# Diffusion kernel “guide”

Diffusion kernels are kernels which "project" information about graphs into $R^n$ so that certain machine learning techniques can be performed.

I have read through this paper and feel fairly comfortable with the theory behind these kernels, but I'm looking for guidance about how they can best be applied.

An example problem I'm facing is that it involves calculating $e^{tA}$ for a large matrix $A$, which is not a trivial task. I know that sometimes finding $e^{tA}\vec{x}$ is a much simpler problem - is this one of those cases? And is the resulting distance I get the best to use, or are there further "fine tuning" methods?

In case it's relevant: my problem is essentially "nearest neighbor". Each example is a "bag" of attributes from a set $S$, where $S$ is structured as an ontology (graph). So I want to find some distance metric that I can apply to my examples, based on the information I get from the graph.

EDIT: Suppose I have two points in $R^n$: $x$ and $y$. I can find the distance between these points by numerous methods; most obviously by using the Euclidean $||x-y||$.

Now suppose my points are not in $R^n$, but rather in an arbitrary graph. How do I find the distance between them? (What does it even mean to say the "distance" between them?) This is the problem that diffusion kernels solve.

I understand at a high level what this solution is, but actually calculating it is harder. So I'm asking for help in figuring out how to calculate this. I think seeing someone step through an example would be ideal, but any guidance about calculation would be helpful.

EDIT 2: We have an ontology like:

         Computer Science
/               \
AI             Theory of CS
/   \               /        \
NLP    Vision     Decidability   Computational Complexity


How similar are "decidability" and "computational complexity"? What a diffusion kernel does is it provides a kernel to project this data into a more easily measurable space.

• I think you're going to have to explain a little more of the context around diffusion kernels and the paper you cite in order for the question to be intelligible. If you could summarize a bit more what you're trying to compute, I think the answers you'll get will likely be more helpful. – Bill Barth Feb 3 '12 at 16:22
• @BillBarth: I have tried to clarify what I'm doing. – Xodarap Feb 3 '12 at 16:46
• So, that's a little more, but how does the matrix exponential fit in? I think we need more details, still. – Bill Barth Feb 3 '12 at 20:38
• @Bill: The diffusion kernel is $e^{tH}$ where H is the Laplacian of the graph. But I'm not really interested in the general problem of solving matrix exponentials, I want a sort of "case study" of when using diffusion kernels is [un]helpful. – Xodarap Feb 5 '12 at 20:07
• It seems to me that you are looking for the nearest neighbor graph of your data, so you can compute the Laplacian and then cluster your data. Is this correct? Maybe you could elaborate on the relationship between your points in $\mathbb{R}^n$ and your graph. – Deathbreath Feb 5 '12 at 22:27

Your samples are subsets of $S$, which is structured according to a graph $G$. The dimensionality of your problem is the cardinality of $S$. If $H$ is the graph Laplacian of $G$, then $\|x-y\|:=\sqrt{\langle x-y|H|x-y\rangle}$ is a metric.
Your kernel could then be $e^{-t\|d\|^2}$ and you do your cluster analysis as everybody else does.
• Thanks, I agree that this is roughly what I need to do at a high level, but I want a lower-level description. E.g. how do you find the optimal $t$? And I'm specifically curious about diffusion kernels, though I know there are many others. – Xodarap Feb 6 '12 at 15:51
• Optimal for what? If you have an exterior measure of quality you should probably use that. There is no lower level description. From your samples $x_i$, compute $$K(x_i,x_j)=e^{-t\langle x_i-x_j|H|x_i-x_j\rangle}$$ or $$K(x_i,x_j)=\langle x_i|e^{-tH}|x_j\rangle$$. Now use PCA, SVM etc. A higher-level description would be that $K(x_i,x_j)$ represents the transition probability from $x_i$ to $x_j$. – Deathbreath Feb 6 '12 at 18:22