Graph Homomorphism Revisited for Graph Matching

Summary: Introduces p-homomorphism and 1-1 p-hom, extending edge-to-path mapping and node similarity for graph matching. Demonstrates NP-completeness even on DAGs, approximation-hardness, and provides provable-approximation algorithms with experimental validation on web-site matching. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10051
Venue: VLDB
Year: 2010
Pagerank: 7.8524059e-05
Overall Rank: 2,938 | 79.57%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,285	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00012833377
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
2,551	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5572574e-05
4,946	Querying Graph Patterns	2011	PODS	5.8149362e-05
5,877	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	5.2916612e-05
6,971	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	4.8792893e-05
7,762	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	4.6583829e-05
7,775	Graph Querying Meets HCI: State of the Art and Future Directions	2017	SIGMOD	4.653773e-05
8,210	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	4.5581054e-05
9,887	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	4.2621158e-05
11,191	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1945683e-05
11,578	BOOMER: A Tool for Blending Visual P-Homomorphic Queries on Large Networks	2020	SIGMOD	4.1945683e-05
11,659	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	4.1945683e-05
11,670	NAVIGATE: Explainable Visual Graph Exploration by Examples	2019	SIGMOD	4.1945683e-05
12,041	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1945683e-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
171	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00038830709
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023598882
572	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019887011
919	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015343179
3,683	Finding replicated web collections	2000	SIGMOD	6.8477289e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
11,961	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB	4.1945683e-05
1,635	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001105793
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
1,720	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010779343
4,807	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9092289e-05
11,559	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1945683e-05
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
5,776	Capturing Topology in Graph Pattern Matching	2012	VLDB	5.3309758e-05
11,565	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1945683e-05