Caltech Logo

H.B. Keller Colloquium

Monday, May 10, 2021
2:00pm to 3:00pm
Add to Cal
Online Event
Convex Graph Parameters and Their Applications
Venkat Chandrasekaran, Professor of Computing and Mathematical Sciences and Electrical Engineering, Computing and Mathematical Sciences Dept., California Institute of Technology,

Inverse problems over graphs arise in many application domains as graphs are widely used to model dependencies among large numbers of interacting entities; examples include gene interaction network
analysis in computational biology, molecular structure comparison problems in chemistry, and community detection in social networks.  To address the combinatorial complexity typically associated with such
problems, we describe a conceptually unified framework based on continuous optimization for the solution of inverse problems over unlabeled graphs.  Our approach is based on the notion of a convex graph invariant, which is a graph parameter that is also a convex function over the space of adjacency matrices.  Several graph
parameters associated with the spectrum, the degree distribution, the stability number, the max-cut value, the isoperimetric number and so on are in fact convex.  We demonstrate the utility of these by deriving tractable convex relaxations for the planted subgraph problem and for obtaining bounds on graph edit distances.

For more information, please contact Diana Bohler by phone at 6262326138 or by email at dbohler@caltech.edu.