Reliable Inference at Scale Using Graph Structure

Abstract

As our world becomes increasingly interconnected, the informational landscape that drives decision-making is marked by ever-expanding scale and interdependencies. Leveraging graph structure, we develop computationally efficient alternatives to canonical subroutines that underlie inference in modern machine learning and optimization infrastructure. We discuss two key directions: First, we optimize graph algorithms for learning from distributed data sources, addressing a key challenge in decentralized settings- namely, identifying simple probabilistic rules for organizing nodes to balance sparsity with reliable connectivity. Our results resolve several open problems related to the exact analysis of connectivity properties in a class of random graph models known as random k-out graphs, widely appearing as heuristics for network design in settings with limited trust. Second, we discuss computationally efficient alternatives to parameter learning in probabilistic graphical models. We develop methods that retain the statistical advantage of classical maximum likelihood estimation while significantly cutting computational costs in the context of high dimensional exponential family models. Summing, our work sheds new light on how the interplay between graph structure and performance can be leveraged to push the frontiers of efficient and provably reliable algorithms.