Comparing stars

TLDR

Graph data are ubiquitous, and graph edit distance is a widely accepted similarity measure, but computing it is NP‑Hard in general. The paper introduces three novel polynomial‑time methods to compute upper and lower bounds on graph edit distance. The authors develop two algorithms, AppFull and AppSub, and evaluate them on real and synthetic datasets to assess bounding graph edit distance. The methods scale well with graph number and size, and their bounds effectively improve filtering and searching in graph databases.

Abstract

Graph data have become ubiquitous and manipulating them based on similarity is essential for many applications. Graph edit distance is one of the most widely accepted measures to determine similarities between graphs and has extensive applications in the fields of pattern recognition, computer vision etc. Unfortunately, the problem of graph edit distance computation is NP-Hard in general. Accordingly, in this paper we introduce three novel methods to compute the upper and lower bounds for the edit distance between two graphs in polynomial time. Applying these methods, two algorithms AppFull and AppSub are introduced to perform different kinds of graph search on graph databases. Comprehensive experimental studies are conducted on both real and synthetic datasets to examine various aspects of the methods for bounding graph edit distance. Result shows that these methods achieve good scalability in terms of both the number of graphs and the size of graphs. The effectiveness of these algorithms also confirms the usefulness of using our bounds in filtering and searching of graphs.