Convex graph invariant relaxations for graph edit distance

DOI10.1007/S10107-020-01564-4zbMATH Open1489.90202arXiv1904.08934OpenAlexW3085534486MaRDI QIDQ2118089FDOQ2118089

Utkan Onur Candogan, Venkat Chandrasekaran

Publication date: 22 March 2022

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

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.

Full work available at URL: https://arxiv.org/abs/1904.08934

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Exact matrix completion via convex optimization
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Convex Analysis
• Rank-Sparsity Incoherence for Matrix Decomposition
• A distance measure between attributed relational graphs for pattern recognition
• Spectra of graphs
• Graph Implementations for Nonsmooth Convex Programs
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite programming relaxations for the quadratic assignment problem
• Convex graph invariants
• ORBITOPES
• The number of maximum independent sets in graphs
• Structural, Syntactic, and Statistical Pattern Recognition
• Edit distance-based kernel functions for structural pattern classification
• A Fast Matching Algorithm for Graph-Based Handwriting Recognition
• A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem
• Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation

Uses Software

• SDPT3
• CVX
• GEDEVO
• C-GRAAL

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)