Theory and Algorithms on the Median Graph. Application to Graph-based Classification and Clustering

Abstract

Donat un conjunt d'objectes, el concepte genèric de mediana està de&#64257;nit com l'objecte amb la suma de distàncies a tot el conjunt, més petita. Sovint, aquest concepte és usat per a obtenir el representant del conjunt. <br/>En el reconeixement estructural de patrons, els grafs han estat usats normalment per a representar objectes complexos. En el domini dels grafs, el concepte de mediana és conegut com median graph. Potencialment, té les mateixes aplicacions que el concepte de mediana per poder ser usat com a representant d'un conjunt de grafs. <br/>Tot i la seva simple de&#64257;nició i les potencials aplicacions, s'ha demostrat que el seu càlcul és una tasca extremadament complexa. Tots els algorismes existents només han estat capaços de treballar amb conjunts petits de grafs, i per tant, la seva aplicació ha estat limitada en molts casos a usar dades sintètiques sense signi&#64257;cat real. Així, tot i el seu potencial, ha restat com un concepte eminentment teòric. <br/>L'objectiu principal d'aquesta tesi doctoral és el d'investigar a fons la teoria i l'algorísmica relacionada amb el concepte de medinan graph, amb l'objectiu &#64257;nal d'extendre la seva aplicabilitat i lliurar tot el seu potencial al món de les aplicacions reals. Per això, presentem nous resultats teòrics i també nous algorismes per al seu càlcul. Des d'un punt de vista teòric aquesta tesi fa dues aportacions fonamentals. Per una banda, s'introdueix el nou concepte d'spectral median graph. Per altra banda es mostra que certes de les propietats teòriques del median graph poden ser millorades sota determinades condicions. Més enllà de les aportacioncs teòriques, proposem cinc noves alternatives per al seu càlcul. La primera d'elles és una conseqüència directa del concepte d'spectral median graph. Després, basats en les millores de les propietats teòriques, presentem dues alternatives més per a la seva obtenció. Finalment, s'introdueix una nova tècnica per al càlcul del median basat en el mapeig de grafs en espais de vectors, i es proposen dos nous algorismes més. <br/>L'avaluació experimental dels mètodes proposats utilitzant una base de dades semi-arti&#64257;cial (símbols grà&#64257;cs) i dues amb dades reals (mollècules i pàgines web), mostra que aquests mètodes són molt més e&#64257;cients que els existents. A més, per primera vegada, hem demostrat que el median graph pot ser un bon representant d'un conjunt d'objectes utilitzant grans quantitats de dades. Hem dut a terme experiments de classi&#64257;cació i clustering que validen aquesta hipòtesi i permeten preveure una pròspera aplicació del median graph a un bon nombre d'algorismes d'aprenentatge.

Given a set of objects, the generic concept of median is de&#64257;ned as the object with the smallest sum of distances to all the objects in the set. It has been often used as a good alternative to obtain a representative of the set. <br/>In structural pattern recognition, graphs are normally used to represent structured objects. In the graph domain, the concept analogous to the median is known as the median graph. By extension, it has the same potential applications as the generic median in order to be used as the representative of a set of graphs. <br/>Despite its simple de&#64257;nition and potential applications, its computation has been shown as an extremely complex task. All the existing algorithms can only deal with small sets of graphs, and its application has been constrained in most cases to the use of synthetic data with no real meaning. Thus, it has mainly remained in the box of the theoretical concepts. <br/>The main objective of this work is to further investigate both the theory and the algorithmic underlying the concept of the median graph with the &#64257;nal objective to extend its applicability and bring all its potential to the world of real applications. To this end, new theory and new algorithms for its computation are reported. From a theoretical point of view, this thesis makes two main contributions. On one hand, the new concept of spectral median graph. On the other hand, we show that some of the existing theoretical properties of the median graph can be improved under some speci&#64257;c conditions. In addition to these theoretical contributions, we propose &#64257;ve new ways to compute the median graph. One of them is a direct consequence of the spectral median graph concept. In addition, we provide two new algorithms based on the new theoretical properties. Finally, we present a novel technique for the median graph computation based on graph embedding into vector spaces. With this technique two more new algorithms are presented. <br/>The experimental evaluation of the proposed methods on one semi-arti&#64257;cial and two real-world datasets, representing graphical symbols, molecules and webpages, shows that these methods are much more ecient than the existing ones. In addition, we have been able to proof for the &#64257;rst time that the median graph can be a good representative of a class in large datasets. We have performed some classi&#64257;cation and clustering experiments that validate this hypothesis and permit to foresee a successful application of the median graph to a variety of machine learning algorithms.