Citation
Candogan, Utkan Onur (2020) Convex Relaxations for Graph and Inverse Eigenvalue Problems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/ZV0DSW58. https://resolver.caltech.edu/CaltechTHESIS:01152020210801253
Abstract
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 SchurHorn 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 SchurHorn 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 SchurHorn 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 SchurHorn orbitope, we also consider outerapproximations based on other convex graph invariants such as the stability number and the maximumcut 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; SchurHorn 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): 
 
Thesis Committee: 
 
Defense Date:  15 August 2019  
Funders: 
 
Record Number:  CaltechTHESIS:01152020210801253  
Persistent URL:  https://resolver.caltech.edu/CaltechTHESIS:01152020210801253  
DOI:  10.7907/ZV0DSW58  
Related URLs: 
 
ORCID: 
 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  13622  
Collection:  CaltechTHESIS  
Deposited By:  Utkan Candogan  
Deposited On:  03 Feb 2020 21:06  
Last Modified:  10 Feb 2020 17:07 
Thesis Files

PDF (Thesis)
 Final Version
See Usage Policy. 3MB 
Repository Staff Only: item control page