Diversified Top-k Subgraph Querying in a Large Graph

Summary: Diversified top-k subgraph querying in large graphs: up to k isomorphic subgraphs maximize coverage. Proposes a level-based algorithm with early termination and a provable approximation; experiments on data show near-optimal results and ~10 ms queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hdfbdd01967334160
Venue: SIGMOD
Year: 2016
Pagerank: 6.097643e-05
Overall Rank: 5,486 | 63.23%
DOI: 10.1145/2882903.2915216

Incoming Non-self Citations Over Time

Authors

1. Zhengwei Yang (Chinese University of Hong Kong)
2. Ada Wai-Chee Fu (Chinese University of Hong Kong)
3. Ruifeng Liu (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{yang_sigmod16,
        title = {{Diversified Top-k Subgraph Querying in a Large Graph}},
        author = {Yang, Zhengwei and Fu, Ada Wai-Chee and Liu, Ruifeng},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915216},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915216},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,882	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.6412354e-05
8,920	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.2361195e-05
9,059	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	5.21427e-05
9,334	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.1794997e-05
10,223	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0460607e-05
11,123	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.9605343e-05
11,491	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.9605343e-05
12,028	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026634326
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022009138
333	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020712452
356	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020086045
439	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018247958
440	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018235529
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017479773
734	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014334121
1,146	Efficient Diversity-Aware Search	2011	SIGMOD	0.00011779564
1,180	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011600363
1,252	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011321716
1,376	Query Preserving Graph Compression	2012	SIGMOD	0.00010857788
1,502	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010431532
1,565	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.00010185615
1,862	DisC Diversity: Result Diversification based on Dissimilarity and Coverage	2013	VLDB	9.4680154e-05
2,192	Top-k Bounded Diversification	2012	SIGMOD	8.8838688e-05
2,251	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7460227e-05
3,992	Diversified Top-k Graph Pattern Matching	2013	VLDB	6.8567907e-05
4,568	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.5171208e-05
4,835	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	6.3793473e-05
5,619	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.0468899e-05
6,784	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.6673728e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
2	10,879	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB
3	10,281	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD
4	6,043	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
5	4,568	Querying Big Graphs within Bounded Resources	2014	SIGMOD
6	440	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
7	3,992	Diversified Top-k Graph Pattern Matching	2013	VLDB
8	11,123	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB
9	1,907	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD
10	3,771	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB