Constraint-based graph matching

Abstract. Measuring graph similarity is a key issue in many applications. We propose a new constraint-based modeling language for defining graph similarity measures by means of constraints. It covers measures based on univalent match-ings, such that each node is matched with at most one node, as well as multivalent matchings, such that a node may be matched with a set of nodes. This language is designed on top of Comet, a programming language supporting both Constraint Programming (CP) and Constraint-Based Local Search (CBLS). Starting from the constraint-based description of the measure, we automatically generate a Comet program for computing the measure. Depending on the measure characteristics, this program either uses CP —which is better suited for computing exact mea-sures such as (sub)graph isomorphism — or CBLS —which is better suited for computing error-tolerant measures such as graph edit distances. First experimen-tal results show the feasibility of our approach.