4
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bill Barth
    Commented Feb 3, 2012 at 16:22
  • $\begingroup$ @BillBarth: I have tried to clarify what I'm doing. $\endgroup$
    – Xodarap
    Commented Feb 3, 2012 at 16:46
  • $\begingroup$ So, that's a little more, but how does the matrix exponential fit in? I think we need more details, still. $\endgroup$
    – Bill Barth
    Commented Feb 3, 2012 at 20:38
  • $\begingroup$ @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. $\endgroup$
    – Xodarap
    Commented Feb 5, 2012 at 20:07
  • $\begingroup$ 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. $\endgroup$
    – Deathbreath
    Commented Feb 5, 2012 at 22:27

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Xodarap
    Commented Feb 6, 2012 at 15:51
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Deathbreath
    Commented Feb 6, 2012 at 18:22
  • $\begingroup$ I'm not sure what to say. I'm asking for a paper which describes their implementation of a diffusion kernel. What you're telling me is completely valid - it's just that I'd rather have a paper describing all of the steps they did instead of enumerate my problems in a comment and have them answered one by one. (Although if I can't find a reference, that's what I may turn to...) $\endgroup$
    – Xodarap
    Commented Feb 6, 2012 at 22:47
  • 1
    $\begingroup$ Have you looked at Gist-kernel ? Note the option "diffusion". $\endgroup$
    – Deathbreath
    Commented Feb 7, 2012 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.