4
$\begingroup$

How can somebody apply PCA on a set of graphs? Is it possible to define a meaningful graph kernel for my problem, and then follow the typical procedure on the derived matrix of pairwise distances (kernel PCA) ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

How can somebody apply PCA on a set of graphs?

It is perfectly legal to apply PCA on a set of graphs. After all, one graph is just a point in a space, and given a distance measure (kernel) in that space you can apply PCA as usual.

Is it possible to define a meaningful graph kernel for my problem, and then follow the typical procedure on the derived matrix of pairwise distances?

That's absolutely fine -- once you have a matrix of pairwise distances you're back to good old PCA.

If you're looking for some interesting kernels I would recommend you to search online for "graph distance measures" or "graph similarity measures," and you will find a lot of them. One particularly easy example is the Hamming distance, which is basically the number of edge additions or deletions needed to transform one graph into another.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer. Commenting on your point about seeing the graph as a point in a space - well I can think of that one such mapping would be using the adjacency matrix rows as coordinates in a high dimensional space. But this becomes a bit problematic when it comes to graphs of different sizes. And particularly when there is no mapping among the nodes of two graphs (modulo the permutations of the nodes) - do you have in mind a more natural instantiation of a graph as a point in space? $\endgroup$
    – Dion
    Commented May 24, 2017 at 7:11
  • 2
    $\begingroup$ @DionysisM Unfortunately I don't think thinking about graphs in terms of coordinates will take you very far. It's important to know the difference between a Euclidean space (where you have lengths and distances and you can actually plot points in it) and a metric space (where you only have distances between points and nothing else). $R^n$ is a Euclidean space while graphs live in a metric space, so there is no way you can map graphs onto $R^n$ without extra assumptions. I'm afraid you'll have to get familiar with the abstract mathematical notions of space and metric. $\endgroup$
    – Pedro Mediano
    Commented May 24, 2017 at 8:41

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.