Extending Graph Patterns with Conditions

Summary: CGPs extend graph patterns with per-edge conditions, so edges exist only if the condition holds, enabling missing-link detection and richer dependencies in compact form. Complexity: linear-time for consistency; NP-complete for matching; NP^p-complete for incremental matching; Pi2-complete for containment; plus practical CGP/multi-CGP matching and incremental optimization with empirical validation on real and synthetic graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h5936b96fad78cf82
Venue: SIGMOD
Year: 2020
Pagerank: 5.5124816e-05
Overall Rank: 7,483 | 49.71%
DOI: 10.1145/3318464.3380585

Incoming Non-self Citations Over Time

Authors

1. Grace Fan (Brown University)
2. Wenfei Fan (Beihang University; Shenzhen University; University of Edinburgh)
3. Yuanhao Li (Shenzhen University; University of Edinburgh)
4. Ping Lu (Beihang University)
5. Chao Tian (Alibaba)
6. Jingren Zhou (Alibaba)

BibTeX Citation

@inproceedings{fan_sigmod20,
        title = {{Extending Graph Patterns with Conditions}},
        author = {Fan, Grace and Fan, Wenfei and Li, Yuanhao and Lu, Ping and Tian, Chao and Zhou, Jingren},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380585},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380585},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,783	Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming	2021	VLDB	6.4133399e-05
7,579	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	5.4908669e-05
11,569	Extending Graph Rules with Oracles	2024	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
155	Common Expression Analysis in Database Applications	1982	SIGMOD	0.0002851688
211	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00024805216
289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021960834
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
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015048943
961	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012830477
1,046	Graphflow: An Active Graph Database	2017	SIGMOD	0.00012316579
1,100	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012007739
1,132	Efficient Exploitation of Similar Subexpressions for Query Processing	2007	SIGMOD	0.00011893781
2,212	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	8.8195478e-05
2,365	Dependencies for Graphs	2017	PODS	8.5625389e-05
2,851	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.9382307e-05
3,027	Functional Dependencies for Graphs	2016	SIGMOD	7.7351194e-05
3,769	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.0282248e-05
12,216	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,245	Discovering Graph Functional Dependencies	2018	SIGMOD
2	12,216	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD
3	4,585	Event Pattern Matching over Graph Streams	2015	VLDB
4	5,606	Capturing Topology in Graph Pattern Matching	2012	VLDB
5	12,071	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD
6	1,318	Incremental Graph Pattern Matching	2011	SIGMOD
7	3,027	Functional Dependencies for Graphs	2016	SIGMOD
8	5,099	Querying Graph Patterns	2011	PODS
9	1,150	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
10	8,986	Adding Counting Quantifiers to Graph Patterns	2016	SIGMOD