NETWORK ALIGNMENT AND STRUCTURED SIGNALS IN RANDOM GRAPHS

Abstract

This thesis advances the theoretical foundations and practical methodologies for spec-tral graph inference in random graph models, with an emphasis on graph alignment, latent structure detection, and multi-graph analysis. Spectral embedding has become a central tool for statistical network analysis due to its efficiency and versatility in tasks such as com- munity detection, anomaly detection, and graph comparison. However, challenges such as vertex misalignment across graphs, noisy or contaminated graph structures, and induced correlations in multi-graph embeddings limit the effectiveness of existing methods. This thesis addresses these challenges through three complementary projects. In the first project, we develop OmniMatch, a novel seeded multiple graph matching algorithm under the d-dimensional Random Dot Product Graph (RDPG) model. We prove that under mild assumptions, OmniMatch leverages s seeds to asymptotically and efficiently achieve perfect alignment of O(sα ) unseeded vertices (where s is the set of seeds) for α < 2∧d/4 across multiple networks even in the presence of no edge correlation. Through simulations and real-data experiments, we demonstrate that correcting vertex misalignment prior to hypothesis testing recovers the statistical power lost due to shuffled nodes. Appli- cations to connectomics and machine translation networks validate the practical utility of the method. The second project investigates the limitations of widely used embedding techniques, Adjacency Spectral Embedding (ASE) and Graph Encoder Embedding (GEE)—in detect- ing dense pseudo-clique structures in RDPGs. We provide theoretical results and extensive simulations showing that in both theory and experiments, we demonstrate that this pair- ing of model and methods can yield worse results than the best existing spectral clique detection methods, demonstrating at once the methods’ potential inability to capture even modestly sized pseudo-cliques and the methods’ robustness to the model contamination giving rise to the pseudo-clique structure. To broaden the analysis, we further evaluate the Variational Graph Auto-Encoder (VGAE) in both simulated and real-world settings. The third project provides a rigorous analysis of induced correlations in joint spec- tral embedding methods for multiple graphs, including Omnibus embedding, joint embed- ding, Multi-RDPG, and multiple adjacency spectral embedding (MASE). Using the COSIE model, we derive a central limit theorem for the distances between score matrices and estab- lish bounds on the correlations induced by the embedding process under both independent and correlated graph settings. We examine how these correlations affect community de- tection in multiple graphs and anomaly detection in temporal graph sequences, providing practical insights into the reliability of multi-graph embeddings. Together, these contributions deepen our understanding of the theoretical properties, strengths, and limitations of spectral graph embedding methods, while also proposing new algorithms that address fundamental challenges in multiple graph inference and latent structure detection. Through a combination of rigorous theory, simulations, and real-world applications—including brain connectomics, social networks, co-authorship networks, and communication networks—this work establishes both theoretical benchmarks and practical tools for analyzing complex networked systems where traditional embedding approaches may be insufficient and where robust alignment and structure recovery are essential for meaningful inference.