Graph homomorphism revisited for graph matching

In a variety of emerging applications one needs to decide whether a graph G matches another Gp, i.e., whether G has a topological structure similar to that of Gp. The traditional notions of graph homomorphism and isomorphism often fall short of capturing the structural similarity in these applications. This paper studies revi-sions of these notions, providing a full treatment from complexity to algorithms. (1) We propose p-homomorphism (p-hom) and 1-1 p-hom, which extend graph homomorphism and subgraph isomor-phism, respectively, by mapping edges from one graph to paths in another, and by measuring the similarity of nodes. (2) We intro-duce metrics to measure graph similarity, and several optimization problems for p-hom and 1-1 p-hom. (3) We show that the deci-sion problems for p-hom and 1-1 p-hom are NP-complete even for DAGs, and that the optimization problems are approximation-hard. (4) Nevertheless, we provide approximation algorithms with prov-able guarantees on match quality. We experimentally verify the effectiveness of the revised notions and the efficiency of our algo-rithms in Web site matching, using real-life and synthetic data. 1