Convex Optimization for Graphons
Abstract
Motivation- Graphs are useful for modeling relationships among large numbers of interacting entities. Due to their flexibility in providing a compact description of such large-scale interactions, graphs are useful in domains as varied as computational biology (gene interaction networks), technological infrastructure (the internet, power grids), and the social sciences (community networks). There are a number of research challenges associated with the use of networks in these and other applications, and many of these may be formulated as inference problems involving graph-valued data. A key conceptual difficulty underlying such inference problems is that of comparing graphs of different sizes. Objective- To address the challenges underlying the comparison of graphs of different sizes, Lovasz and his collaborators developed the framework of graphons around two decades ago. Graphons provide a systematic way to compare and evaluate the ‘distance’ between graphs of different sizes by introducing a suitable metric space over the collection of all finite graphs. Graphons have had notable impact in numerous areas of mathematics such as extremal combinatorics and theoretical computer science. Our objective is to develop a systematic optimization framework for solving large-scale graph problems, with the key requirement that the methods are compatible with the metric structure underlying the space of graphons. Approach- In this proposal, we seek a framework for convex optimization over graphons. Specifically, we aim at a convex programming framework that blends seamlessly with the existing theory of graphons by developing mathematical and computational foundations for sequences of convex functions that are invariant under node relabeling and that are continuous with respect to the metric structure of graphons. Building on this notion, we describe in this proposal a collection of research questions aimed at developing a convex optimization framework for graphons. Successfully addressing these questions will substantially broaden the applicability of graphon methodology in domains involving inference problems over graph-valued data.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 29, 2024
- Source ID
- FA95502310070
Entities
People
- Venkat Chandrasekaran
Organizations
- Air Force Office of Scientific Research
- California Institute of Technology
- United States Air Force