Adding Counting Quantifiers to Graph Patterns

Summary: Proposes quantified graph patterns (QGPs) with counting edge quantifiers, enabling universal/existential quantification and numeric aggregates. Quantified matching is NP-complete without negation and DP-complete for general QGPs; it weaves quantifier checks into subgraph isomorphism and delivers parallel scalable algorithms for quantified graph association rules. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hc7e32a80453c2942
Venue: SIGMOD
Year: 2016
Pagerank: 5.2452044e-05
Overall Rank: 8,976 | 39.66%
DOI: 10.1145/2882903.2882937

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Yinghui Wu (Washington State University)
3. Jingbo Xu (Beihang University; University of Edinburgh)

BibTeX Citation

@inproceedings{fan_sigmod16,
        title = {{Adding Counting Quantifiers to Graph Patterns}},
        author = {Fan, Wenfei and Wu, Yinghui and Xu, Jingbo},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882937},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882937},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,293	Capturing Associations in Graphs	2020	VLDB	5.3612871e-05
10,153	Threshold Queries in Theory and in the Wild	2022	VLDB	5.0715586e-05
11,550	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.9793485e-05
11,563	Extending Graph Rules with Oracles	2024	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.00064420972
511	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017061883
620	Mining Quantitative Association Rules in Large Relational Tables	1996	SIGMOD	0.00015502611
1,046	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012319866
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011627329
1,317	Incremental Graph Pattern Matching	2011	SIGMOD	0.00011050011
1,506	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010452205
4,441	SocialScope: Enabling Information Discovery on Social Content Sites	2009	CIDR	6.5991946e-05
4,858	Association Rules with Graph Patterns	2015	VLDB	6.3793644e-05
6,824	Ratio Rules: A New Paradigm for Fast, Quantifiable Data Mining	1998	VLDB	5.6715478e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,551	Querying Big Graphs within Bounded Resources	2014	SIGMOD
2	12,065	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD
3	1,317	Incremental Graph Pattern Matching	2011	SIGMOD
4	8,293	Capturing Associations in Graphs	2020	VLDB
5	3,979	Diversified Top-k Graph Pattern Matching	2013	VLDB
6	5,605	Capturing Topology in Graph Pattern Matching	2012	VLDB
7	5,096	Querying Graph Patterns	2011	PODS
8	1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
9	4,858	Association Rules with Graph Patterns	2015	VLDB
10	7,478	Extending Graph Patterns with Conditions	2020	SIGMOD