H.B. Keller Colloquium

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.