Convex graph invariant relaxations for graph edit distance

DOI10.1007/S10107-020-01564-4MaRDI QIDQ2118089zbMATH OpenOpenAlexFDO

Authors Utkan Onur Candogan, Venkat Chandrasekaran

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.08934, https://authors.library.caltech.edu/96713/

zbMATH Keywords

convex optimizationsemidefinite programmingmajorizationstrongly regular graphsmaximum cutstability number

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Semidefinite programming (90C22)

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.

Recommendations

• A Quadratic Programming Approach to the Graph Edit Distance Problem
• Convex graph invariants
• A survey of graph edit distance
• On convex relaxation of graph isomorphism
• Improved Graph Edit Distance Approximation with Simulated Annealing

Cites work

• scientific article; zbMATH DE number 3982880 (Why is no real title available?)
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• scientific article; zbMATH DE number 6262292 (Why is no real title available?)
• A distance measure between attributed relational graphs for pattern recognition
• A fast matching algorithm for graph-based handwriting recognition
• A low-dimensional semidefinite relaxation for the quadratic assignment problem
• Convex Analysis
• Convex graph invariants
• Edit distance-based kernel functions for structural pattern classification
• Exact matrix completion via convex optimization
• Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation
• Graph implementations for nonsmooth convex programs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Maxima for Graphs and a New Proof of a Theorem of Turán
• ORBITOPES
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Rank-Sparsity Incoherence for Matrix Decomposition
• Robust optimization
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Semidefinite programming relaxations for the quadratic assignment problem
• Spectra of graphs
• Structural, Syntactic, and Statistical Pattern Recognition
• The number of maximum independent sets in graphs

Describes a project that uses

Uses Software

• C-GRAAL
• GEDEVO
• CVX
• SDPT3

This page was built for publication: Convex graph invariant relaxations for graph edit distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118089)