Seeded Recovery Approaches for Networks

Understanding the structure and dynamics of complex networks is a central challenge across disciplines such as biology, sociology, and computer science. This thesis develops seeded methods for network inference, leveraging partial label and correspondence information to improve recovery of latent structure beyond what is achievable by purely unsupervised approaches. We study two fundamental tasks---\textbf{community detection} and \textbf{graph alignment}---within variants of the Stochastic Block Model (SBM) and Correlated Stochastic Block Model (CSBM) that incorporate partial supervision, treating both the connected and sparse regimes. Our first contribution introduces quasi-stationary distribution (QSD) methods for semi-supervised community detection in the connected seeded SBM. By treating revealed nodes as absorbing states of a random walk, we define transition submatrices whose principal eigenvectors encode community information. We prove that the resulting QSD estimator, combined with a direct voting component, achieves the optimal minimax error rate $n^{-(1+o(1))(\sqrt{a}-\sqrt{b})^2/2}$ and show via a new equivariance argument that this rate is unchanged by partial label information in the connected regime. Our second contribution characterizes exact graph matching in the almost fully seeded correlated SBM, where all but $|\mathcal{U}| = n^{1-\alpha}$ vertex correspondences are revealed. We prove that the information-theoretic threshold shifts smoothly from $\lambda s^2 > 1$ (the unseeded condition) to $\lambda s^2 > 1-\alpha$, and present four polynomial-time algorithms---including neighborhood-overlap heuristics, an $\ell_1$ LP relaxation, and a Frank--Wolfe approximation---that achieve this threshold. Our third contribution extends these results to the simultaneous exact recovery of both the vertex permutation and community labeling in the seeded correlated SBM. We characterize the joint recovery threshold and show that community signal and graph correlation combine additively in the recovery exponent, generalizing the unseeded results of Gaudio, R\'{a}cz, and Sridhar to the partially revealed regime. Our fourth contribution addresses partial recovery in the sparse seeded SBM with $k$ balanced communities, where exact recovery is unachievable. We propose a plurality voting algorithm and prove it achieves accuracy strictly above $1/k$ whenever $a > b$, including below the Kesten--Stigum threshold, extending prior majority-voting results for $k = 2$ to general $k$.