Back to search

Georgia Institute of Technology

Statistical Inference and Computational Methods on Graphs with Geometric Structures

Abstract

dc:description.abstract

This 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

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhang, Shenduo. Statistical Inference and Computational Methods on Graphs with Geometric Structures. Georgia Institute of Technology, 2026. https://hdl.handle.net/1853/82195