Extending Theories of the Graph Matching Problem and Its Variants

Abstract

Graphs serve as powerful tools for modeling complex real-world relationships, making reliable statistical inference on graphs a crucial task. A fundamental problem in this domain is the graph matching problem, which seeks to align node labels across graphs while minimizing structural and feature discrepancies. In this thesis, I investigate algorithms for the graph matching problem and one of its key variants, the subgraph detection problem. I develop theoretical frameworks that leverage signals from a clustered, vertex-aligned collection of graphs to accurately recover node labels in a newly shuffled network and classify this new network into one of the clusters. Additionally, I propose a novel approach for detecting multiple instances of a noisily embedded template graph within a large background graph. Furthermore, I explore the relationship between the anonymization time and the mixing time of a specific class of Markovian noise applied to graph edges. Beyond these contributions, I address several related challenges in graph matching and its related optimization algorithms, offering new insights into their theoretical and practical aspects. To validate our methodologies, I provide rigorous theoretical justifications and conduct extensive experiments using both simulated and real-world network data. These findings demonstrate the effectiveness of the proposed approaches, bridging the gap between theoretical advancements and practical applications in graph inference.