Convex graph invariants

DOI10.1137/100816900zbMATH Open1250.05091arXiv1012.0623OpenAlexW2022330001MaRDI QIDQ2913268FDOQ2913268

Authors: Venkat Chandrasekaran, Pablo A. Parrilo, Alan S. Willsky 

Publication date: 26 September 2012

Published in: SIAM Review (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1012.0623

Recommendations

• Convexity in Graphs and Hypergraphs
• INVARIANTS OF GRAPHS
• scientific article; zbMATH DE number 1743966
• scientific article; zbMATH DE number 1439489
• Convexity in oriented graphs
• scientific article; zbMATH DE number 3880762
• scientific article; zbMATH DE number 3880749
• The convexity spectra of graphs
• Convex graphon parameters and graph norms
• On the convexity number of graphs

zbMATH Keywords

convex optimizationgraph samplinggraph deconvolutionspecral invariants

Mathematics Subject Classification ID

Convex programming (90C25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75) Convex functions and convex programs in convex geometry (52A41)

Cited In (11)

• Turán theorems and convexity invariants for directed graphs
• Conic formulations of graph homomorphisms
• Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation
• Convex graph invariant relaxations for graph edit distance
• Optimization and highly informative graph invariants
• Graph implementations for nonsmooth convex programs
• Hodge-Kodaira decomposition of evolving neural networks
• On the connectedness of spectral sets and irreducibility of spectral cones in Euclidean Jordan algebras
• Concentration of the Frobenius norm of generalized matrix inverses
• Spectral sets and functions on Euclidean Jordan algebras
• Convexity properties of the canonical \(S\)-graphs

This page was built for publication: Convex graph invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2913268)