A Caltech Library Service

Convex Relaxations for Graph and Inverse Eigenvalue Problems


Candogan, Utkan Onur (2020) Convex Relaxations for Graph and Inverse Eigenvalue Problems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/ZV0D-SW58.


This thesis is concerned with presenting convex optimization based tractable solutions for three fundamental problems:

1. Planted subgraph problem: Given two graphs, identifying the subset of vertices of the larger graph corresponding to the smaller one.

2. Graph edit distance problem: Given two graphs, calculating the number of edge/vertex additions and deletions required to transform one graph into the other.

3. Affine inverse eigenvalue problem: Given a subspace ε ⊂ 𝕊ⁿ and a vector of eigenvalues λ ∈ ℝⁿ, finding a symmetric matrix with spectrum λ contained in ε.

These combinatorial and algebraic problems frequently arise in various application domains such as social networks, computational biology, chemoinformatics, and control theory. Nevertheless, exactly solving them in practice is only possible for very small instances due to their complexity. For each of these problems, we introduce convex relaxations which succeed in providing exact or approximate solutions in a computationally tractable manner.

Our relaxations for the two graph problems are based on convex graph invariants, which are functions of graphs that do not depend on a particular labeling. One of these convex relaxations, coined the Schur-Horn orbitope, corresponds to the convex hull of all matrices with a given spectrum, and plays a prominent role in this thesis. Specifically, we utilize relaxations based on the Schur-Horn orbitope in the context of the planted subgraph problem and the graph edit distance problem. For both of these problems, we identify conditions under which the Schur-Horn orbitope based relaxations exactly solve the corresponding problem with overwhelming probability. Specifically, we demonstrate that these relaxations turn out to be particularly effective when the underlying graph has a spectrum comprised of few distinct eigenvalues with high multiplicities. In addition to relaxations based on the Schur-Horn orbitope, we also consider outer-approximations based on other convex graph invariants such as the stability number and the maximum-cut value for the graph edit distance problem. On the other hand, for the inverse eigenvalue problem, we investigate two relaxations arising from a sum of squares hierarchy. These relaxations have different approximation qualities, and accordingly induce different computational costs. We utilize our framework to generate solutions for, or certify unsolvability of the underlying inverse eigenvalue problem.

We particularly emphasize the computational aspect of our relaxations throughout this thesis. We corroborate the utility of our methods with various numerical experiments.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Convex optimization; semidefinite programming; convex relaxations; Schur-Horn orbitope; graph theory, inverse eigenvalue problem
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Chandrasekaran, Venkat
Thesis Committee:
  • Vaidyanathan, P. P. (chair)
  • Chandrasekaran, Venkat
  • Hassibi, Babak
  • Wierman, Adam C.
  • Low, Steven H.
Defense Date:15 August 2019
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0210
Record Number:CaltechTHESIS:01152020-210801253
Persistent URL:
Related URLs:
URLURL TypeDescription adapted for Chapter 2. adapted for Chapter 3. adapted for Chapter 4.
Candogan, Utkan Onur0000-0002-1416-4909
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13622
Deposited By: Utkan Candogan
Deposited On:03 Feb 2020 21:06
Last Modified:18 Dec 2020 18:35

Thesis Files

PDF (Thesis) - Final Version
See Usage Policy.


Repository Staff Only: item control page