The graph alignment problem: fundamental limits and efficient algorithms
This work addresses a core problem in network analysis with potential applications in domains like social networks or bioinformatics, but it appears incremental as it builds on existing graph alignment frameworks.
The thesis investigates the graph alignment problem, a noisy variant of graph isomorphism, by establishing fundamental information-theoretic limits and developing algorithms with high-probability guarantees for recovering alignments in random planted graphs.
This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves most of the edges. Focusing on the planted version where the graphs are random, we are interested in understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data. For these algorithms, we give some high probability guarantees on the regime in which they succeed or fail.