Graph Homomorphism Revisited for Graph Matching

Summary: Introduces p-homomorphism and 1-1 p-homomorphism, mapping edges to paths and quantifying node similarity beyond homomorphism/isomorphism. Establishes NP-completeness and approximation hardness—even on DAGs—while providing guaranteed approximations validated for website matching. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10242
Venue: VLDB
Year: 2010
Pagerank: 8.209788e-05
Overall Rank: 2,718 | 81.36%
DOI: 10.14778/1920841.1920986

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Harbin Engineering University; University of Edinburgh)
2. Jianzhong Li (Harbin Engineering University)
3. Shuai Ma (University of Edinburgh)
4. Hongzhi Wang (Harbin Engineering University)
5. Yinghui Wu (University of Edinburgh)

BibTeX Citation

@article{fan_vldb10,
        title = {{Graph Homomorphism Revisited for Graph Matching}},
        author = {Fan, Wenfei and Li, Jianzhong and Ma, Shuai and Wang, Hongzhi and Wu, Yinghui},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {1161--1172},
        doi = {10.14778/1920841.1920986},
        url = {https://doi.org/10.14778/1920841.1920986},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,394	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.0001093153
2,285	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.8052998e-05
4,748	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	6.5251089e-05
4,986	Querying Graph Patterns	2011	PODS	6.4120976e-05
6,728	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	5.7898807e-05
7,664	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.5720259e-05
7,845	Graph Querying Meets HCI: State of the Art and Future Directions	2017	SIGMOD	5.5332653e-05
8,206	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	5.4666548e-05
10,037	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	5.1729561e-05
11,394	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	5.093636e-05
11,774	BOOMER: A Tool for Blending Visual P-Homomorphic Queries on Large Networks	2020	SIGMOD	5.093636e-05
11,854	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	5.093636e-05
11,865	NAVIGATE: Explainable Visual Graph Exploration by Examples	2019	SIGMOD	5.093636e-05
12,239	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
187	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00026138589
444	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00018350865
591	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.0001603683
776	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014110016
3,725	Finding replicated web collections	2000	SIGMOD	7.171112e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD
2	12,159	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB
3	1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB
4	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
5	1,296	Incremental Graph Pattern Matching	2011	SIGMOD
6	3,908	Diversified Top-k Graph Pattern Matching	2013	VLDB
7	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
8	1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
9	5,484	Capturing Topology in Graph Pattern Matching	2012	VLDB
10	11,762	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD