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: 11174
Venue: VLDB
Year: 2015
Pagerank: 9.7730473e-05
Overall Rank: 2,021 | 85.96%
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,125	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013829006
1,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
1,715	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010776518
1,906	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010135267
2,882	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	7.9666138e-05
2,963	Subgraph Matching: on Compression and Computation	2018	VLDB	7.8061004e-05
3,119	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.5393376e-05
3,488	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	7.0460627e-05
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
4,554	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0839934e-05
5,030	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.7445683e-05
5,120	Association Rules with Graph Patterns	2015	VLDB	5.6754325e-05
5,490	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	5.4788004e-05
5,502	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	5.4730826e-05
5,809	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB	5.3175972e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
5,933	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2620152e-05
6,436	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0554554e-05
7,091	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	4.8304411e-05
7,304	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	4.7628386e-05
8,786	Adding Counting Quantifiers to Graph Patterns	2016	SIGMOD	4.4467423e-05
9,375	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3452177e-05
10,062	Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings	2026	SIGMOD	4.1905499e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,139	An Extensive Experimental Study of Indexes in Continuous Subgraph Matching:[Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.1905499e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1905499e-05
10,855	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.1905499e-05
10,982	Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching	2024	SIGMOD	4.1905499e-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
387	Graph Summarization with Bounded Error	2008	SIGMOD	0.00024682268
435	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00023268266
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014759406
1,572	Query Preserving Graph Compression	2012	SIGMOD	0.00011296109
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
5,871	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	5.2912806e-05
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362
1,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
1,125	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013829006
5,530	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	5.4562393e-05
3,119	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	7.5393376e-05
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
4,486	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1413967e-05
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047