The Graph Edit Distance ({GED}) is an important metric for measuring the similarity between two (labeled) graphs. It is defined as the minimum cost required to convert one graph into another through a series of (elementary) edit operations. Its effectiveness in assessing the similarity of large graphs is limited by the complexity of its exact calculation, which is {NP}-hard theoretically and computationally challenging in practice. The latter can be mitigated by switching to the Graph Similarity Search under {GED} constraints, which determines whether the edit distance between two graphs is below a given threshold. A popular framework for solving Graph Similarity Search under {GED} constraints in a graph database for a query graph is the filter-and-verification framework. Filtering discards unpromising graphs, while the verification step certifies the similarity between the filtered graphs and the query graph. To improve the filtering step, we define a lower bound based on an integer linear programming formulation. We prove that this lower bound dominates the effective branch match-based lower bound and can also be computed efficiently. Consequently, we propose a graph similarity search algorithm that uses a hierarchy of lower bound algorithms and solves a novel integer programming formulation that exploits the threshold parameter. An extensive computational experience on a well-assessed test bed shows that our approach significantly outperforms the state-of-the-art algorithm on most of the examined thresholds.<\/p>\n","protected":false},"excerpt":{"rendered":"
The Graph Edit Distance ({GED}) is an important metric for measuring the similarity between two (labeled) graphs. It is defined as the minimum cost required to convert one graph into another through a series of (elementary) edit operations. Its effectiveness in assessing the similarity of large graphs is limited by the complexity of its exact calculation, which is {NP}-hard theoretically and computationally challenging in practice. The latter can be mitigated […]<\/p>\n","protected":false},"author":12,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[30],"class_list":["post-32204","publication","type-publication","status-publish","hentry","publication-type-article"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32204","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/publication"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/12"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32204\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=32204"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=32204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}