DROPS

Document

Research

An Efficient Heuristic for Graph Edit Distance

Authors: Xiaoyang Chen, Yujia Wang, Hongwei Huo, and Jeffrey Scott Vitter

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract

The graph edit distance (GED) is a flexible distance measure widely used in many applications. Existing GED computation methods are usually based upon the tree-based search algorithm that explores all possible vertex (or edge) mappings between two compared graphs. During this process, various GED lower bounds are adopted as heuristic estimations to accelerate the tree-based search algorithm. For the first time, we analyze the relationship among three state-of-the-art GED lower bounds, label edit distance (LED), Hausdorff edit distance (HED), and branch edit distance (BED). Specifically, we demonstrate that BED(G, Q) ≥ HED(G, Q) and BED(G, Q) ≥ LED(G, Q) for any two undirected graphs G and Q. Furthermore, for BED we propose an efficient heuristic BED^+ for improving the tree-based search algorithm. Extensive experiments on real and synthetic datasets confirm that BED^+ achieves smaller deviation and larger solvable ratios than LED, HED and BED when they are employed as heuristic estimations. The source code is available online.

Cite as

Xiaoyang Chen, Yujia Wang, Hongwei Huo, and Jeffrey Scott Vitter. An Efficient Heuristic for Graph Edit Distance. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:OASIcs.Grossi.1,
  author =	{Chen, Xiaoyang and Wang, Yujia and Huo, Hongwei and Vitter, Jeffrey Scott},
  title =	{{An Efficient Heuristic for Graph Edit Distance}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{1:1--1:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.1},
  URN =		{urn:nbn:de:0030-drops-238004},
  doi =		{10.4230/OASIcs.Grossi.1},
  annote =	{Keywords: Graph edit distance, Label edit distance, Hausdorff edit distance, Branch edit distance, Tree-based search, Heuristics}
}

Search Results

Documents authored by Wang, Yujia

An Efficient Heuristic for Graph Edit Distance

Abstract

Cite as

Thanks for your feedback!

Could not send message