PhD Thesis Defense

Thursday August 15, 2019 1:00 PM

Convex Relaxations for Graph and Inverse Eigenvalue Problems

Speaker: Utkan Onur Candogan, Electrical Engineering, California Institute of Technology
Location: Annenberg 314

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

  • Planted subgraph problem: Given two graphs, identify the subset of vertices of the larger graph corresponding to the smaller one.
  • Graph edit distance problem: Given two graphs, calculate the number of edge/vertex additions and deletions required to transform one graph into the other.
  • Subspace constrained inverse eigenvalue problem: Given a subspace E ⊂ Sn and a vector of eigenvalues λ ∈ Rn, find a symmetric matrix with spectrum λ contained in E.
  • These combinatorial/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 notorious difficulty. 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 outer-approximations of the set of adjacency matrices representing the underlying graphs. In particular, we investigate a convex outer-approximation that exclusively depends on the graph spectrum for the planted subgraph problem, whereas we additionally consider outer-approximations based on the stability number and the maximum-cut value for the graph edit distance problem. For both of these problems, we identify conditions under which our graph spectrum based relaxations exactly solve the corresponding problem with overwhelming probability. Specifically, we demonstrate that the graph spectrum based relaxations turn out to be particularly effective when the underlying graph has a spectrum comprised of few distinct eigenvalues with high multiplicities. 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.

    Series Thesis Seminar

    Contact: Tanya Owen at 626-395-8817