Graph inference and graph matching problems : Theory and algorithms
Marcelo Fiori
PhD thesis from Universidad de la República (Uruguay). Facultad de Ingeniería. IIE - May. 2015
Advisor: Pablo Musé
Co-advisor: Guillermo Sapiro
Research Group(s): (unspecified)
Department(s): Procesamiento de Señales
Download the publication : Fio15.pdf [5.2Mo]  


Almost every field has some problems related with graphs or networks. From natural examples in physics and mathematics, to applications in medicine and signal processing, graphs are either a very powerful tool, or a very rich object of interest. In this thesis we address two classes of graph-related problems. First, we focus on graph-inference problems, consisting in the estimation of a graph or network from a dataset. In this part of the manuscript, we modify the existing formulations of the inference problem to incorporate prior topological information of the graph, and to jointly infer several graphs, in a collaborative way. We apply these techniques to infer genetic regulation networks, brain connectivity patterns, and economy-related networks. We also present a new problem, which consists in the estimation of mobility patterns from highly asynchronous and incomplete data. We give a rst formulation of the problem with its corresponding optimization, and present results for airplane routes and New York taxis mobility patterns. The second class consists of the so-called graph matching problems. In this type of problems two graphs are given, and the objective is to nd the best alignment between them. This problem is of great interest both from an algorithmic and theoretical point of view, besides the very important applications. Its interest and diculty lie in the combinatorial nature of the problem: the cost of seeking among all the possible permutations grows exponentially with the number of nodes, and hence becomes intractable even for small graphs. First, we focus on the algorithmic aspect of the graph matching problem. We present two methods based on relaxations of the discrete optimization problem. The rst one is inspired in ideas from the sparse modeling community, and the second one is based on a theorem presented in this manuscript. The importance of these methods is illustrated with several applications along the chapter. Finally, we address some theoretical aspects about graph matching and other related problems. The main question tackled in the last chapter is the following: when do the graph matching problem and its convex relaxation have the same solution? A probabilistic approach is rst given, showing that, asymptotically, the most common convex relaxation fails, while a non-convex relaxation succeeds with probability one if the graphs to be matched are correlated enough, showing a phase-transition type of behavior. On the other hand, a deterministic approach is presented, stating conditions on the eigenvectors and eigenvalues for guaranteeing the correctness of the convex relaxation solution. Other results and conjectures relating the spectrum and symmetry of a graph are presented as well.

Additional data


BibTex references

Descargar BibTex bibtex

Other publications in the database

» Marcelo Fiori