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.1155396e-05
Overall Rank: 5,477 | 63.18%
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,609	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	5.4847975e-05
8,891	Efficient Top-k Frequent Subgraph Mining Using Tight Upper and Lower Bounds	2025	VLDB	5.2559789e-05
9,030	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	5.2340466e-05
9,296	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.1991444e-05
10,186	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0651993e-05
11,053	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.9793485e-05
11,432	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.9793485e-05
11,978	MIDAS: Towards Efficient and Effective Maintenance of Canned Patterns in Visual Graph Query Interfaces	2021	SIGMOD	4.9793485e-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.00026700508
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021969641
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020765078
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020124083
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014363536
1,145	Efficient Diversity-Aware Search	2011	SIGMOD	0.00011824078
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011627329
1,244	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011353487
1,375	Query Preserving Graph Compression	2012	SIGMOD	0.00010877488
1,506	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010452205
1,572	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.00010197978
1,850	DisC Diversity: Result Diversification based on Dissimilarity and Coverage	2013	VLDB	9.5038109e-05
2,174	Top-k Bounded Diversification	2012	SIGMOD	8.917444e-05
2,235	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.7779518e-05
3,979	Diversified Top-k Graph Pattern Matching	2013	VLDB	6.8802947e-05
4,551	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.5401646e-05
4,817	Taming Subgraph Isomorphism for RDF Query Processing	2015	VLDB	6.3985024e-05
5,605	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.0695806e-05
6,760	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD	5.6887265e-05

Semantically Similar Papers

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