A graph distance metric combining maximum common subgraph and minimum common supergraph

Pattern Recognition LettersPublished 1 May 2001

Mirtha-Lina Fernández, Gabriel Valiente

DOI10.1016/s0167-8655(01)00017-4

Source URL

Citations205

SJR quartileQ1

SJR score1.00

SNIP1.43

TL;DR

A new graph distance metric is proposed for measuring similarities between objects represented by attributed relational graphs that can be computed by a straightforward extension of any algorithm that implements error-correcting graph matching, when run under an appropriate cost function, and the extension only takes time linear in the size of the graphs.

Abstract

The relationship between two important problems in pattern recognition using attributed relational graphs, the maximum common subgraph and the minimum common supergraph of two graphs, is established by means of simple constructions, which allow to obtain the maximum common subgraph from the minimum common supergraph, and vice versa. On this basis, a new graph distance metric is proposed for measuring similarities between objects represented by attributed relational graphs. The proposed metric can be computed by a straightforward extension of any algorithm that implements error-correcting graph matching, when run under an appropriate cost function, and the extension only takes time linear in the size of the graphs.

Keywords

Computer Science

IEEE Transactions on Pattern Analysis and Machine IntelligenceA graduated assignment algorithm for graph matching

1,098 Citations1996Steven Gold, Anand Rangarajan

A graduated assignment algorithm for graph matching is presented which is fast and accurate even in the presence of high noise, and not restricted to any special class of graph, is applied to subgraph isomorphism, weighted graph matching, and attributed relational graph matching.

Pattern Recognition LettersA graph distance metric based on the maximal common subgraph

737 Citations1998Horst Bunke, Kim Shearer

It is formally shown that the new distance measure is a metric, based on the maximal common subgraph of two graphs, which is superior to edit distance based measures in that no particular edit operations together with their costs need to be defined.

IEEE Transactions on Pattern Analysis and Machine IntelligenceStructural Descriptions and Inexact Matching

542 Citations1981Linda G. Shapiro, Robert M. Haralick

The structural description of an object and the concepts of exact and inexact matching of two structural descriptions are formally defined and the formula for the expected number of nodes in the tree for backtracking alone and with a forward checking algorithm is developed.

View PDF

Pattern Recognition LettersOn a relation between graph edit distance and maximum common subgraph

519 Citations1997Horst Bunke

In this paper a particular cost function for graph edit distance is introduced, and it is shown that under this cost functiongraph edit distance computation is equivalent to the maximum common subgraph problem.

Pattern Recognition LettersInexact graph matching for structural pattern recognition

477 Citations1983Horst Bunke, Gudrun Allermann

This paper is concerned with the inexact matching of attributed, relational graphs for structural pattern recognition and the matching procedure is based on a state space search utilizing heuristic information.

IEEE Transactions on Pattern Analysis and Machine IntelligenceA new algorithm for error-tolerant subgraph isomorphism detection

335 Citations1998Bettina Messmer, Horst Bunke

A new algorithm for error-correcting subgraph isomorphism detection from a set of model graphs to an unknown input graph is proposed based on a compact representation of the model graphs that can be combined with a future cost estimation method that greatly improves its run-time performance.

IEEE Transactions on Systems Man and CyberneticsError-Correcting Isomorphisms of Attributed Relational Graphs for Pattern Analysis

325 Citations1979Wen‐Hsiang Tsai, King‐Sun Fu

The pattern deformational model proposed by Tsai and Fu is extended so that numerical attributes and probability or density distributions can be introduced into primitives and relations in a nonhierarchical relational graph.

Software Practice and ExperienceBacktrack search algorithms and the maximal common subgraph problem

292 Citations1982James J. McGregor

This algorithm has been used successfully as a component of a program for analysing chemical reactions and enumerating the bond changes which have taken place and its use in the problem of finding the maximal common subgraph of two graphs is described.

IEEE Transactions on Pattern Analysis and Machine IntelligenceError correcting graph matching: on the influence of the underlying cost function

227 Citations1999Horst Bunke

It is shown that, for a given cost function, there are an infinite number of other cost functions that lead, for any given pair of graphs, to the same optimal error correcting matching.

CALCOLOA note on the derivation of maximal common subgraphs of two directed or undirected graphs

226 Citations1973Giorgio Levi

A technique is described by which this problem of finding maximal common subgraphs of two given graphs can be stated as a problem of deriving maximal compatibility classes and the same technique is shown to apply to the classical subgraph isomorphism problem.