Diversified Top-k Graph Pattern Matching

Summary: Recasts simulation-based graph pattern matching as top-k retrieval for a designated output node, avoiding full match enumeration via early-terminating relevance-ranked algorithms. For diversified ranking, proves NP-completeness and provides a guaranteed approximation and early-terminating heuristic. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10828
Venue: VLDB
Year: 2013
Pagerank: 7.0262215e-05
Overall Rank: 3,908 | 73.19%
DOI: 10.14778/2536258.2536263

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Xin Wang (University of Edinburgh)
3. Yinghui Wu (University of California Santa Barbara)

BibTeX Citation

@article{fan_vldb13,
        title = {{Diversified Top-k Graph Pattern Matching}},
        author = {Fan, Wenfei and Wang, Xin and Wu, Yinghui},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {13},
        pages = {1510--1521},
        doi = {10.14778/2536258.2536263},
        url = {https://doi.org/10.14778/2536258.2536263},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,006	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012699518
4,631	Interactive Summarization and Exploration of Top Aggregate Query Answers	2018	VLDB	6.595034e-05
5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.2436385e-05
7,664	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB	5.5720259e-05
8,871	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	5.35418e-05
9,131	TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database	2023	SIGMOD	5.3184767e-05
9,999	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.1814573e-05
10,037	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	5.1729561e-05
10,301	Towards Selecting Informative Alternative Relational Query Plans for Database Education	2026	SIGMOD	5.093636e-05
10,606	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	5.093636e-05
11,075	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	5.093636e-05
11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	5.093636e-05
11,854	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
77	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00037048607
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,454	Diversifying Top-K Results	2012	VLDB	0.00010739504
1,908	Max-Sum Diversification, Monotone Submodular Functions and Dynamic Updates	2012	PODS	9.5010932e-05
2,220	Identifying Meaningful Return Information for XML Keyword Search	2007	SIGMOD	8.9277765e-05
4,221	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD	6.8233111e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,221	Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs	2008	SIGMOD
2	5,484	Capturing Topology in Graph Pattern Matching	2012	VLDB
3	7,094	Top-K Structural Diversity Search in Large Networks	2013	VLDB
4	1,296	Incremental Graph Pattern Matching	2011	SIGMOD
5	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
6	7,664	Optimal Enumeration: Efficient Top-k Tree Matching	2015	VLDB
7	11,762	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD
8	1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
9	5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
10	10,606	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB