I have a collection of graph objects of variable size (input) which are each paired to another graph of variable size (output). The task is, given an input graph, produce the most likely output graph.

I have been looking at 'structured output' techniques such as SSVM but as far as I can tell, they all act on outputs of fixed size (or at least a size that matches the input size, i.e. sequence tagging). Are there any tools that can map an input to a structured object of arbitrary size?


You better try graph embedding and for that I propose going through Horst Bunke from University of Bern who has been doing it for years. Just search him in google scholar and go through his publication network (co-authors,cited papers, citing papers,etc) for example this and this as more classic papers or this as an exact answer to your question. I am pretty confident you will find your solution as it's exactly his research direction. I am on mobile so referencing is difficult now but I can update my answer later.

The other point that I would like to mention is that graph embedding has two kinds:

  1. Embedding the vertices (nodes) of one graph into a n-dimensional space i.e. each vector will be a node of the graph. (see this)
  2. Embedding a dataset of graphs into a n-dimensional space in which each vector will be an entire graph.

You need the second one.

The other thing worth to mention is looking at the problem from Network Science point of view in which the statistical and structural of a graph is widely studied. There are plenty of graph/network measures which are less or more tolerante to the number of nodes e.g. Clustering Coefficient. Using them as features can be fed to a classifier to see how it works.

The last but not the least is what you actually asked! What you are looking for is called Graph Kernel. It is nothing but the definition of the ML-known concept Kernel but on graphs. So kernel methods can get benefit of that by skipping the feature extraction step (like what I suggested above) and directly work with structural inputs. For this purpose I would suggest that you equip yourself with the graph kernels e.g. this paper.

Good luck!

  • $\begingroup$ Thanks! From my understanding, these methods allow one to map an input graph to another graph that has been previously seen in the data. But is it possible for these techniques to map an unseen input to an unseen yet likely graph (for example, a graph that combines elements of two others) based on the patterns learned from the training instances? I suppose we could call this somewhat of a generative task... $\endgroup$ – Carlos G. Oliver Jan 26 '18 at 22:07
  • $\begingroup$ It is certainly possible. These methods are about mapping a graph to a point in n-dimensional space. Like what u asked. So if you choose ur straauctural graph representation, you will end up with proper results. As long as u do not confuse between vertex embedding and graph embedding. $\endgroup$ – Kasra Manshaei Jan 26 '18 at 23:35

Your Answer

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

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