I have a question for graph machine learning gurus :). For this project I'm working on, I need to be able to learn similarity between typed graphs. By typed I mean that every vertex and every edge of the graph has it's type. Also, both nodes and vertices can be attributed (assigned with some "key-value" attributes).

Now, I could employ "standard" feature-based supervised ML to perform this task, but then I would have to come up with good features that represent similarity between two typed graphs. In this case I would operate with the computed features and not at the level of graphs themselves directly.

I've read about graph kernels (and their corresponding kernel machines learning algorithms) that sort of deal precisely with this issue - they handle graphs directly, instead of inventing numeric features that reflect similarity. What I also figured out is that these graph kernel methods are used to classify graphs. I couldn't fugre out how to use them to learn a good "similarity function" between a pair of graphs? Are kernel methods even the right way to go for this type of problem? I'd really appreciate any advice.

Are there perhaps any good/well-known "unsupervised" algorithm for measuring the similarity between two typed graphs? The similarity measure should consider both structure and semantics of the graphs (by semantics I mean types and attributes assigned to nodes/edges).

I would also be very interested in some algorithms that identify inexact matches between such graphs (supervised, unsupervised, any). Any recommendations for those? Any advice would be really appreciated!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.