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.1126446e-05
Overall Rank: 5,481 | 63.17%
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
7,616	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.4822011e-05
8,900	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.2534908e-05
9,038	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	5.2315688e-05
9,306	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.1966832e-05
10,189	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0628015e-05
11,062	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.9769913e-05
11,438	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.9769913e-05
11,984	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.9769913e-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.00026688651
289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021960834
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020756016
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020116134
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018278591
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018190518
489	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017440023
737	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014357361
1,145	Efficient Diversity-Aware Search	2011	SIGMOD	0.00011818487
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011621825
1,247	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011348258
1,375	Query Preserving Graph Compression	2012	SIGMOD	0.00010872356
1,507	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010447258
1,572	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.0001019315
1,851	DisC Diversity: Result Diversification based on Dissimilarity and Coverage	2013	VLDB	9.499317e-05
2,177	Top-k Bounded Diversification	2012	SIGMOD	8.9132232e-05
2,238	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7738068e-05
3,980	Diversified Top-k Graph Pattern Matching	2013	VLDB	6.87704e-05
4,550	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.5380867e-05
4,819	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	6.3954734e-05
5,606	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.0667077e-05
6,767	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.6860336e-05

Semantically Similar Papers

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