Models and algorithms for computing the common labelling of a set of attributed graphs

In some methodologies, it is needed a consistent common labelling between the vertices of a graph set, for instance, to compute a representative of a set of graphs. This is an NP-complete problem with an exponential computational cost depending on the number of nodes and the number of graphs. In the current paper, we present two new methodologies to compute a sub-optimal common labelling. The former focuses in extending the Graduated Assignment algorithm, although the methodology could be applied to other probabilistic graph-matching algorithms. The latter goes one step further and computes the common labelling whereby a new iterative sub-optimal algorithm. Results show that the new methodologies improve the state of the art obtaining more precise results than the most recent method with similar computational cost.

► One of the most important points on computing a graph prototype is to compute the common labelling among all graphs in the set. Most of the approaches up to date perform pair-wise graph matching operations in order to compute the common labelling. We present a set of methods to compute the common labelling considering all the knowledge of the set.
► The first two methods we present are based on computing a probability node assignation hyper-cube. This methods offer very good performance, however the high computational cost makes its use unfeasible with large graph sets.
► The third method we present is based on a new probabilistic framework. The method offers similar performance as the two initial methods but with a much lower computational cost.
► The results of the evaluation show that the methods we present offer best performance than up to date methods.