Graph homomorphism revisited for graph matching
Open Access
- 1 September 2010
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 3 (1-2) , 1161-1172
Abstract
In a variety of emerging applications one needs to decide whether a graph G matches another G p , i.e. , whether G has a topological structure similar to that of G p . 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.Keywords
This publication has 21 references indexed in Scilit:
- Information preserving XML schema embeddingACM Transactions on Database Systems, 2008
- Fragment-based approximate retrieval in highly heterogeneous XML collectionsData & Knowledge Engineering, 2008
- A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web SearchingSIAM Review, 2004
- CLUSTERING OF WEB DOCUMENTS USING A GRAPH MODEL2003
- Finding replicated Web collectionsACM SIGMOD Record, 2000
- Approximations of Weighted Independent Set and Hereditary Subset ProblemsJournal of Graph Algorithms and Applications, 2000
- Mirror, mirror on the Web: a study of host pairs with replicated contentComputer Networks, 1999
- Syntactic clustering of the WebComputer Networks and ISDN Systems, 1997
- An efficient transitive closure algorithm for cyclic digraphsInformation Processing Letters, 1994
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992