Georgia Institute of Technology
Statistical Inference and Computational Methods on Graphs with Geometric Structures
Abstract
dc:description.abstractThis thesis studies statistical and computational limits in random graphs with latent geometric structure. The unifying framework is the observation chain \(Z\to X\to A\): latent variables generate an identifiable geometric object, and the observed graph is a noisy or thresholded view of that object. The first part studies planted dense cycles and proves low-degree computational thresholds and information-theoretic thresholds for detection and recovery, revealing both detection--recovery and statistical--computational gaps. The second part studies high-dimensional random geometric graphs. It proves rate--distortion lower bounds for latent inner-product recovery and a matching spectral upper bound, up to logarithmic factors, for spherical hard-threshold graphs. The final part treats bipartite latent geometric graphs, where the identifiable target is a rectangular cross-Gram matrix. It gives rate--distortion lower bounds governed by the effective dimension of the rectangular low-rank variety and a spectral recovery guarantee based on the symmetric dilation of the centered biadjacency matrix. Together, these results identify when latent geometry is statistically recoverable, when efficient algorithms succeed, and when statistical-to-computational gaps arise.
Degree
thesis:*- Name thesis:degree_name
- Machine Learning, PhD
- Department thesis:degree_department
- Mathematics
- Grantor
- Georgia Institute of Technology
- Year dc:date.issued
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Zhang, Shenduo
- Advisor dc:contributor.advisor
-
- Mao, Cheng
- Committee members dc:contributor.committeemember
-
- Koltchinskii, Vladimir
- Liao, Wenjing
- McKenna, Benjamin
- Alexander Wein
Rights
- Language dc:language.iso
- English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/82195