CIF: Small: Projective limits of sparse graphs

Northeastern University, Boston MA

Investigators

Abstract

The prediction and control of many phenomena of utmost societal importance, such as wars and pandemics, deal with massive volumes of relational data. These relational data often take the form of networks or graphs. To make the analysis of these massive graphs tractable, one typically assumes that their size is infinite. However, this assumption often overlooks a crucial point that these limits may be ill-defined or simply non-existent because real-world networks are sparse -- having relatively few connections -- but the theory of sparse graph limits remains poorly understood, next to non-existent. Therefore, drawing conclusions about real-world sparse networks based on their infinite-size idealizations can be quite misleading. This project seeks to address this problem by developing a novel approach to the theory of sparse graph limits, an approach called "graphides." If successful, this project will lead to rigorous prediction guarantees in applications spanning areas such as neuroscience, graph embedding, machine learning, and routing in telecommunication networks. Graphides are conceptually similar to "graphons" -- limits of dense graphs -- in that they are essentially the connection probability functions in random graph models with latent variables. Unlike graphons, however, graphides are defined within latent spaces of infinite volume to achieve graph sparsity. The primary methods used to demonstrate the convergence of sparse graphs to graphides are rooted in the theory of projective limits, a generalization of the Kolmogorov extension theorem that establishes the conditions for the existence of a stochastic process as the limit of a family of finite-dimensional distributions. The overarching objective of the project is to identify categories of sparse random graph models that have graphides as their limits. To achieve this, sub-goals include the technical development of the general projective graph limit methodology and its application to graphons, graphexes, and graphides. By applying this methodology to a collection of latent-space models, including random hyperbolic graphs -- a highly influential model of real-world networks developed in the investigator's previous NSF-funded research -- the project aims to demonstrate that these models have graphides as their limits and identify these graphides. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.