Graph Homomorphism Revisited for Graph Matching

Wenfei Fan, Jianzhong Li, Shuai Ma, Hongzhi Wang, Yinghui Wu

Research output: Contribution to journalArticlepeer-review


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 revisions 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 isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the similarity of nodes. (2) We introduce metrics to measure graph similarity, and several optimization problems for p-hom and 1-1 p-hom. (3) We show that the decision 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 provable guarantees on match quality. We experimentally verify the effectiveness of the revised notions and the efficiency of our algorithms in Web site matching, using real-life and synthetic data.
Original languageEnglish
Pages (from-to)1161-1172
Number of pages12
JournalProceedings of the VLDB Endowment (PVLDB)
Issue number1
Publication statusPublished - 2010


Dive into the research topics of 'Graph Homomorphism Revisited for Graph Matching'. Together they form a unique fingerprint.

Cite this