Well Robert , it has been done with trees 

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

then it is doable for any representation of data pattern (statistical).

Eg: Undirected   - Markov

OR Bayesian networks

Multicolored graphs (be it nodes or edges) are used !!

https://en.wikipedia.org/wiki/Graph_coloring

Roberto,

Can you impose a "universe" on your graphs?  For example, latent semantic analysis (LSA) analyzes the co-occurrence of words in documents. The analysis cannot include all words nor all documents, rather the corpus is considered to define the universe of words and documents. To make queries work in practice, unknown words are simply ignored. You could apply LSA to your graphs if the nodes "mean" the same thing across models; documents would be graphs, nodes would be words, and a "co-occurrence" would be noted for both nodes that share an edge. LSA isn't designed for classification per se (ie., it produces similarities between words and/or documents), but you can use it for classification by comparing a new graph to all the existing graphs of a class and classifying the new graph into the class that is generally most similar.  You could also use naive Bayes, which is commonly applied to classify documents according to the words in the document (again, bounded by the "universe" of the corpus). Actually, I guess you could use any machine learning method (which fits the data).

If nodes don't mean the same thing across graphs in the way that words mean the same thing (usually) across documents, then either there are some features of the graphs that do have shared meaning or else the graphs are not comparable.  If the former case, your problem is to extract the features (number of nodes, whether a particular shape is present, etc.). Then you can apply LSA, Naive Bayes, etc. by substituting "feature" for "word" in the above discussion. 

If the graphs cannot be compared in any way then I think you can rule out any possibility of being able to apply any analytic technique to your problem because there are no predictor data.

If imposing a "universe" bothers you because new cases may fall outside that universe, then I think your problem becomes one of sample size. How many graphs do you need (and how costly is it to gather a new graph) to have most of the variability in your true universe? In most problems, quite a bit of the variation is present in a surprisingly small training sample.  But if you need a bigger sample, then get a big sample (or else you know why you couldn't do this). My other comment is that machine learning models tend to be fairly robust to missing data (so if you have a new graph with 4 known features and 1 known feature, classification based on the 4 known features could still be effective).

However, there might be ways to try to effectively model unknown features.  For example, in naive Bayesian analysis of text, there are techniques for handling unknown words.  You could assign the word to the most common word.  Or, even better, you could identify the part of speech of the word and use that to predict.  In your case, with features of graphs, you could try to find the known feature most similar to the unknown feature and predict as if that feature were present.

Thank you very much.

I will take a look at the papers, specially to those about  mollecular structures classification.

It is difficult to create a universum of my problem.

Currently I have several graphs whose vertex represent entities (persons, bank accounts, phone numbers, neighborhood,...). Every person has edges with his friends, telephone number, bank account and neiborhood, .... (different persons can share a phone number or bank account, ...)

I would like to classify different kinds of relationship between persons. For example, if both persons have a lot of friends in common they are probably friends. If both persons share a phone number they are probably family,...

Until now I have used hand made features:

-Number of friends in common.

-Boolean telling if they share a phone number.

...

And after that I have been using different machine learning algorithms (Deep Neural Nets, Kernel methods,  ...)

But my grpahs are going to receive more information with new kinds of  vertices and many different classification tasks. So it is impossible to think features to every classification task and I wander if it is possible use directly the graphs, for example vectoricing the graphs to a fixed size vector or to create a kernel function to compare them.

It seems like your problem falls under the pattern mining aspect of machine learning (not classification or regression).

Your problem description falls into one of the classic problems of Social Network Analysis. A reading of published material on this topic would certainly help you with this problem. This topic is quickly becoming a vast subject and there are several books on them too.

Check this paper, it may help~

This is a recent NIPS2016 paper.

https://arxiv.org/pdf/1606.09375.pdf

Caffe is a very powerfull framework of deep learning.

I believe that Caffe is an interesting tool for your application. See:

http://caffe.berkeleyvision.org/