CaltechAUTHORS
  A Caltech Library Service

Convex Graph Invariant Relaxations For Graph Edit Distance

Candogan, Utkan Onur and Chandrasekaran, Venkat (2019) Convex Graph Invariant Relaxations For Graph Edit Distance. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20190626-090040899

[img] PDF - Submitted Version
See Usage Policy.

1922Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190626-090040899

Abstract

The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex relaxations for obtaining lower bounds on graph edit distance. These relaxations can be tailored to the structural properties of the particular graphs via convex graph invariants. Specific examples that we highlight in this paper include constraints on the graph spectrum as well as (tractable approximations of) the stability number and the maximum-cut values of graphs. We prove under suitable conditions that our relaxations are tight (i.e., exactly compute the graph edit distance) when one of the graphs consists of few eigenvalues. We also validate the utility of our framework on synthetic problems as well as real applications involving molecular structure comparison problems in chemistry.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1904.08934arXivDiscussion Paper
ORCID:
AuthorORCID
Candogan, Utkan Onur0000-0003-3920-402X
Additional Information:The authors were supported in part by NSF grants CCF-1350590 and CCF-1637598, by AFOSR grant FA9550-16-1-0210, and by a Sloan research fellowship.
Funders:
Funding AgencyGrant Number
NSFCCF-1350590
NSFCCF-1637598
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0210
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:convex optimization; majorization; maximum cut; semidefinite programming; stability number; strongly regular graphs
Record Number:CaltechAUTHORS:20190626-090040899
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20190626-090040899
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96713
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:26 Jun 2019 16:05
Last Modified:26 Jun 2019 16:05

Repository Staff Only: item control page