Modern inference problems often involve randomly generated data with structure that is not directly observed. In network data, the structure may take the form of hidden communities or unknown correspondences between vertices across correlated observations of the same underlying network. In statistical models, a low-dimensional parameter of interest may be obscured by an unknown and potentially high-dimensional component of the data distribution. Ignoring this structure can lead to overly pessimistic conclusions, while modeling every unknown component explicitly may be infeasible. A central challenge is therefore to identify structural properties that enable inference without requiring complete knowledge of the data-generating process.

This thesis develops algorithmic and statistical methods for inference in various structured probabilistic models. One direction concerns the recovery of latent combinatorial structure in random graphs, including graph matching and community detection in correlated and growing network models such as correlated stochastic block models and the preferential attachment block model. We establish recovery guarantees, including guarantees without computational constraints, and develop efficient algorithms. A second direction concerns inference under structured distributional uncertainty, including the construction of optimal adaptive confidence intervals in the Gaussian mean-shift contamination model and the estimation of watermark proportions in language-model-generated text. Together, these results show how structures under random observations help design provable algorithms for recovering hidden objects and estimating parameters.