Graph based classification and learning
Graphs are a powerful representation for structured information, i.e. information that can be easily characterized by its subparts and the relations between these subparts.
The classification of input samples represented by graphs is not trivial, since the most commonly used classifiers are based on a vectorial representation. The comparison of two graphs can be performed using graph matching techniques, but they are in the general case very expensive computationally; the research activity of the MIVIA lab on this topic has involved the definition of fast algorithms to make the computational cost acceptable for real applications.
Besides the classification, graphs can be used also for the problem of inductive learning, i.e. given a set of example graphs divided into classes, finding a suitable description of the characteristics of each class, that can be used to classify future samples. The MIVIA lab research activity has been focused on the formulation on the learning problem in terms of graphs, using a special kind of generalized graphs as class descriptions, and in the development of learning algorithms based on this representation.