Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs

Summary: BoostIso exploits vertex relationships to prune duplicate work in backtracking-based subgraph isomorphism. Experiments on real graphs show speedups for existing algorithms, up to orders of magnitude on graphs with dense vertex relationships. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11173
Venue: VLDB
Year: 2015
Pagerank: 9.8081235e-05
Overall Rank: 2,007 | 86.04%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Xuguang Ren
2. Junhu Wang

Incoming Citations (Sorted by Pagerank)

Showing 29 of 29 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
1,775	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010602927
1,924	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010077055
2,912	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	7.9130459e-05
2,997	Subgraph Matching: on Compression and Computation	2018	VLDB	7.7559339e-05
3,187	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.4136521e-05
3,641	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	6.8884895e-05
4,205	Association Rules with Graph Patterns	2015	VLDB	6.3597474e-05
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05
4,556	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0883757e-05
4,836	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.8896897e-05
5,499	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	5.4750222e-05
5,728	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	5.3507988e-05
5,811	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB	5.317401e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
5,932	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2670741e-05
6,441	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0603113e-05
7,100	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	4.8326259e-05
7,307	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	4.7674113e-05
8,866	Adding Counting Quantifiers to Graph Patterns	2016	SIGMOD	4.4323126e-05
9,366	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3493859e-05
10,062	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	4.1945683e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,139	An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.1945683e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1945683e-05
10,851	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.1945683e-05
10,979	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
388	Graph Summarization with Bounded Error	2008	SIGMOD	0.00024662272
435	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00023260172
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014765816
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
1,635	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001105793

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
5,877	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	5.2916612e-05
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
5,521	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	5.4614637e-05
3,187	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.4136521e-05
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
1,635	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001105793
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05