Adding Counting Quantifiers to Graph Patterns

Wenfei Fan, Yinghui Wu, Jingbo Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

This paper proposes quantified graph patterns (QGPs), an extension of graph patterns by supporting simple counting quantifiers on edges. We show that QGPs naturally express universal and existential quantification, numeric and ratio aggregates, as well as negation. Better still, the increased expressivity does not come with a much higher price. We show that quantified matching, i.e., graph pattern matching with QGPs, remains NP-complete in the absence of negation,and is DP-complete for general QGPs. We show how quantified matching can be conducted by incorporating quantifier checking into conventional subgraph isomorphism methods.We also develop parallel scalable algorithms for quantified matching. As an application of QGPs, we introduce quantified graph association rules defined with QGPs, to identify potential customers in social media marketing. Using real-life and synthetic graphs, we experimentally verify the effectiveness of QGPs and the scalability of our algorithms.
Original languageEnglish
Title of host publicationACM SIGMOD Conference on Management of Data (SIGMOD 2016)
Number of pages16
ISBN (Print)978-1-4503-3531-7
Publication statusPublished - 2016
Event2016 ACM SIGMOD Conference on Management of Data - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016


Conference2016 ACM SIGMOD Conference on Management of Data
Abbreviated titleSIGMOD 2016
Country/TerritoryUnited States
CitySan Francisco
Internet address


Dive into the research topics of 'Adding Counting Quantifiers to Graph Patterns'. Together they form a unique fingerprint.

Cite this