CaltechTHESIS
  A Caltech Library Service

Convex Relaxations for Graph and Inverse Eigenvalue Problems

Citation

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

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 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
Funders:
Funding AgencyGrant Number
NSF1350590
NSF1637598
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0210
Record Number:CaltechTHESIS:01152020-210801253
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:01152020-210801253
DOI:10.7907/ZV0D-SW58
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/16M1075144DOIArticle adapted for Chapter 2.
https://arxiv.org/pdf/1904.08934.pdfarXivArticle adapted for Chapter 3.
https://arxiv.org/pdf/1911.02225.pdfarXivArticle adapted for Chapter 4.
ORCID:
AuthorORCID
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
Collection:CaltechTHESIS
Deposited By: Utkan Candogan
Deposited On:03 Feb 2020 21:06
Last Modified:10 Feb 2020 17:07

Thesis Files

[img]
Preview
PDF (Thesis) - Final Version
See Usage Policy.

3MB

Repository Staff Only: item control page