Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching

Summary: Introduces vertex-equivalence techniques to speed subgraph search and matching. Static equivalence among query-graph vertices yields a fixed, efficient matching order; dynamic equivalence among data-graph candidates prunes redundant search paths, delivering large speedups over state-of-the-art. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6156
Venue: SIGMOD
Year: 2021
Pagerank: 7.4136521e-05
Overall Rank: 3,187 | 77.83%
DOI: 10.1145/3448016.3457265

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 35 of 35 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,001	Neural Subgraph Counting with Wasserstein Estimator	2022	SIGMOD	7.7404487e-05
4,968	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	5.7956205e-05
5,728	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	5.3507988e-05
5,926	RapidFlow: An Efficient Approach to Continuous Subgraph Matching	2022	VLDB	5.271318e-05
6,281	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.128862e-05
6,289	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	5.1275309e-05
6,395	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.0829204e-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
7,934	Fast Local Subgraph Counting	2024	VLDB	4.613363e-05
8,031	BSX : Subgraph Matching with Batch Backtracking Search	2025	SIGMOD	4.6018906e-05
8,490	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	4.499438e-05
9,727	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	4.2942813e-05
9,730	TC-Match: Fast Time-constrained Continuous Subgraph Matching	2024	VLDB	4.2942813e-05
9,934	MAVIS: Materialized View for Subgraph Matching	2026	SIGMOD	4.2496728e-05
9,935	Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach	2025	SIGMOD	4.2482599e-05
10,014	BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching	2026	SIGMOD	4.1945683e-05
10,096	NeuSO: Neural Optimizer for Subgraph Queries	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,163	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.1945683e-05
10,199	R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization	2026	SIGMOD	4.1945683e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	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,292	Aquila: A High-Concurrency System for Incremental Graph Query	2026	VLDB	4.1945683e-05
10,300	Scalable Approximate Biclique Counting over Large Bipartite Graphs	2026	VLDB	4.1945683e-05
10,308	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1945683e-05
10,632	Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach	2025	VLDB	4.1945683e-05
10,708	Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences	2025	VLDB	4.1945683e-05
10,733	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	4.1945683e-05
10,848	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	4.1945683e-05
10,851	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.1945683e-05
11,303	Density Personalized Group Query	2023	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
203	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034889335
331	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00027214222
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
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
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
900	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015495155
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
1,635	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001105793
1,924	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010077055
2,007	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.8081235e-05
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,720	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	6.8192237e-05
4,072	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.4727847e-05
5,877	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	5.2916612e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
2,007	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.8081235e-05
3,036	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6735171e-05
11,570	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD	4.1945683e-05
6,281	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.128862e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
10,708	Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences	2025	VLDB	4.1945683e-05
4,494	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	6.1414196e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907