Optimization Online


Convex Graph Invariants

Venkat Chandrasekaran(venkatc***at***mit.edu)
Pablo A. Parrilo(parrilo***at***mit.edu)
Alan S. Willsky(willsky***at***mit.edu)

Abstract: The structural properties of graphs are usually characterized in terms of invariants, which are functions of graphs that do not depend on the labeling of the nodes. In this paper we study convex graph invariants, which are graph invariants that are convex functions of the adjacency matrix of a graph. Some examples include functions of a graph such as the maximum degree, the MAXCUT value (and its semidefinite relaxation), and spectral invariants such as the sum of the $k$ largest eigenvalues. Such functions can be used to construct convex sets that impose various structural constraints on graphs, and thus provide a unified framework for solving a number of interesting graph problems via convex optimization. We give a representation of all convex graph invariants in terms of certain elementary invariants, and describe methods to compute or approximate convex graph invariants tractably. We also compare convex and non-convex invariants, and discuss connections to robust optimization. Finally we use convex graph invariants to provide efficient convex programming solutions to graph problems such as the deconvolution of the composition of two graphs into the individual components, hypothesis testing between graph families, and the generation of graphs with certain desired structural properties.

Keywords: Graphs; graph invariants; convex optimization; spectral invariants; majorization; robust optimization; graph deconvolution; graph sampling; graph hypothesis testing

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Robust Optimization

Citation: LIDS technical report 2855, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology.

Download: [PDF]

Entry Submitted: 12/12/2010
Entry Accepted: 12/12/2010
Entry Last Modified: 12/12/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society