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: 10052
Venue: VLDB
Year: 2010
Pagerank: 7.8463193e-05
Overall Rank: 2,943 | 79.55%
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,280	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00012838714
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
2,557	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5484449e-05
4,949	Querying Graph Patterns	2011	PODS	5.8090034e-05
5,871	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	5.2912806e-05
6,965	BOOMER: Blending Visual Formulation and Processing of P-Homomorphic Queries on Large Networks	2018	SIGMOD	4.8759021e-05
7,761	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	4.6543114e-05
7,777	Graph Querying Meets HCI: State of the Art and Future Directions	2017	SIGMOD	4.6493104e-05
8,209	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	4.5537353e-05
9,886	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	4.2580321e-05
11,193	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1905499e-05
11,582	BOOMER: A Tool for Blending Visual P-Homomorphic Queries on Large Networks	2020	SIGMOD	4.1905499e-05
11,664	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	4.1905499e-05
11,675	NAVIGATE: Explainable Visual Graph Exploration by Examples	2019	SIGMOD	4.1905499e-05
12,049	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.1905499e-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
172	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00038837872
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023592024
576	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019858777
916	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015326675
3,685	Finding replicated web collections	2000	SIGMOD	6.8392492e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,125	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013829006
11,969	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB	4.1905499e-05
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
1,806	Incremental Graph Pattern Matching	2011	SIGMOD	0.00010478244
4,748	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9432853e-05
11,563	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1905499e-05
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
5,786	Capturing Topology in Graph Pattern Matching	2012	VLDB	5.3256482e-05
11,569	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1905499e-05