Functional Dependencies for Graphs

Summary: Proposes GFDs, a class of graph functional dependencies unifying attribute-value and topological constraints, subsuming CFDs. Complexity: coNP/NP-complete; the approach provides parallel scalable algorithms for violation detection on large graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0fa516796d48fbcb
Venue: SIGMOD
Year: 2016
Pagerank: 7.7387829e-05
Overall Rank: 3,026 | 79.66%
DOI: 10.1145/2882903.2915232

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 = {{Functional Dependencies for Graphs}},
        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.2915232},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915232},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,364	Dependencies for Graphs	2017	PODS	8.5665938e-05
2,851	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.9419904e-05
3,767	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.0315534e-05
5,798	Normalizing Property Graphs	2023	VLDB	5.9905343e-05
6,525	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.756805e-05
7,015	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.6210836e-05
7,226	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5810344e-05
7,243	Discovering Graph Functional Dependencies	2018	SIGMOD	5.5768239e-05
7,342	Discovering Association Rules from Big Graphs	2022	VLDB	5.5480127e-05
7,478	Extending Graph Patterns with Conditions	2020	SIGMOD	5.5150923e-05
8,293	Capturing Associations in Graphs	2020	VLDB	5.3612871e-05
8,398	Deducing Certain Fixes to Graphs	2019	VLDB	5.3399392e-05
8,590	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB	5.3071244e-05
8,687	Knowledge Graph Exploration Systems: are we lost?	2022	CIDR	5.2905577e-05
9,732	Explaining GNN-based Recommendations in Logic	2025	VLDB	5.1349531e-05
9,806	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1257999e-05
9,967	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.1038322e-05
10,186	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.0651993e-05
10,640	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.9793485e-05
10,720	Structural Normalization of Property Graphs	2026	VLDB	4.9793485e-05
11,121	User-Centric Property Graph Repairs	2025	SIGMOD	4.9793485e-05
11,186	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9793485e-05
11,428	Versatile Property Graph Transformations	2025	VLDB	4.9793485e-05
11,550	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.9793485e-05
11,558	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	4.9793485e-05
11,563	Extending Graph Rules with Oracles	2024	VLDB	4.9793485e-05
11,724	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	4.9793485e-05
11,876	PGE: Robust Product Graph Embedding Learning for Error Detection	2022	VLDB	4.9793485e-05
11,961	Temporal Dependencies for Graphs	2021	SIGMOD	4.9793485e-05
11,966	GRIP: Constraint-based Explanation of Missing Answers for Graph Queries	2021	SIGMOD	4.9793485e-05
11,985	Structural Generalizability: The Case of Similarity Search	2021	SIGMOD	4.9793485e-05
12,030	GEDet: Detecting Erroneous Nodes with A Few Examples	2021	VLDB	4.9793485e-05
12,154	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	4.9793485e-05
12,210	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
328	Declarative Information Extraction Using Datalog with Embedded Extraction Predicates	2007	VLDB	0.00020928928
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
511	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017061883
1,046	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012319866
1,572	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.00010197978
1,710	A Normal Form for XML Documents	2002	PODS	9.8199787e-05
2,423	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.4877894e-05
2,573	Minimal MapReduce Algorithms	2013	SIGMOD	8.2821647e-05
3,066	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.6877117e-05
3,317	Keys for Graphs	2015	VLDB	7.436464e-05
5,953	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.9359492e-05
6,150	DREAM: Distributed RDF Engine with Adaptive Query Planner and Minimal Communication	2015	VLDB	5.8701541e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,478	Extending Graph Patterns with Conditions	2020	SIGMOD
2	8,293	Capturing Associations in Graphs	2020	VLDB
3	7,287	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
4	6,761	Propagating Functional Dependencies with Conditions	2008	VLDB
5	1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB
6	12,210	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD
7	11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
8	2,364	Dependencies for Graphs	2017	PODS
9	2,098	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
10	7,243	Discovering Graph Functional Dependencies	2018	SIGMOD