Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 7, 2012 | Submitted + Published
Journal Article Open

Convex Graph Invariants


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 we describe methods to compute or approximate convex graph invariants tractably. We discuss the interesting subclass of spectral invariants, and also compare convex and nonconvex invariants. 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.

Additional Information

© 2012 Society for Industrial and Applied Mathematics. Received by the editors December 3, 2010; accepted for publication (in revised form) December 5, 2011; published electronically August 7, 2012. This work was partially supported by AFOSR grant FA9550-08-1-0180, by a MURI through ARO grant W911NF-06-1-0076, by a MURI through AFOSR grant FA9550-06-1-0303, and by NSF grant FRG 0757207.

Attached Files

Published - Chandrasekaran2012p19511SIAM_Review.pdf

Submitted - cpw_cgi_preprint10.pdf


Files (1.1 MB)
Name Size Download all
504.9 kB Preview Download
546.1 kB Preview Download

Additional details

August 19, 2023
October 20, 2023