Mining and Indexing Graphs for Supergraph Search

Summary: Supergraph search (SPS) on graph databases; subgraph/supergraph checks are NP-hard, motivating index-based SPS. Proposes subgraph mining optimizing both filtering and prefix-sharing gains, LW-index, and two approximations (1-1/e, 1/4); yields 3-10× SPS speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10932
Venue: VLDB
Year: 2013
Pagerank: 5.8535203e-05
Overall Rank: 6,520 | 55.27%
DOI: 10.14778/2536206.2536211

Incoming Non-self Citations Over Time

Authors

1. Dayu Yuan (Pennsylvania State University)
2. Prasenjit Mitra (Pennsylvania State University)
3. C. Lee Giles (Pennsylvania State University)

BibTeX Citation

@article{yuan_vldb13,
        title = {{Mining and Indexing Graphs for Supergraph Search}},
        author = {Yuan, Dayu and Mitra, Prasenjit and Giles, C. Lee},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {10},
        doi = {10.14778/2536206.2536211},
        url = {https://doi.org/10.14778/2536206.2536211},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,477	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	7.3791229e-05
11,793	IDAR: Fast Supergraph Search Using DAG Integration	2020	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021152829
431	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018577017
664	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015167825
2,328	Towards Graph Containment Search and Indexing	2007	VLDB	8.745748e-05
3,431	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.4189541e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,522	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS
2	3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
3	3,477	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB
4	6,631	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD
5	2,328	Towards Graph Containment Search and Indexing	2007	VLDB
6	591	Substructure Similarity Search in Graph Databases	2005	SIGMOD
7	3,311	Connected Substructure Similarity Search	2010	SIGMOD
8	11,072	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB
9	4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
10	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD