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: 5321
Venue: SIGMOD
Year: 2016
Pagerank: 7.9083516e-05
Overall Rank: 2,973 | 79.61%
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,324	Dependencies for Graphs	2017	PODS	8.7506505e-05
2,798	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	8.1129891e-05
3,709	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.1780227e-05
5,690	Normalizing Property Graphs	2023	VLDB	6.1205402e-05
6,403	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.8859374e-05
6,876	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.7483615e-05
7,083	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.7075402e-05
7,099	Discovering Graph Functional Dependencies	2018	SIGMOD	5.7043774e-05
7,330	Discovering Association Rules from Big Graphs	2022	VLDB	5.6435171e-05
7,365	Extending Graph Patterns with Conditions	2020	SIGMOD	5.6329929e-05
8,113	Capturing Associations in Graphs	2020	VLDB	5.484341e-05
8,225	Deducing Certain Fixes to Graphs	2019	VLDB	5.4624971e-05
8,419	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB	5.4282511e-05
8,520	Knowledge Graph Exploration Systems: are we lost?	2022	CIDR	5.4119882e-05
9,554	Explaining GNN-based Recommendations in Logic	2025	VLDB	5.2528121e-05
9,627	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.2434488e-05
9,999	Discovering Top-k Relevant and Diversified Rules	2024	SIGMOD	5.1814573e-05
10,452	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	5.093636e-05
10,538	Structural Normalization of Property Graphs	2026	VLDB	5.093636e-05
10,681	User-Centric Property Graph Repairs	2025	SIGMOD	5.093636e-05
10,763	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	5.093636e-05
11,069	Versatile Property Graph Transformations	2025	VLDB	5.093636e-05
11,212	Capturing More Associations by Referencing External Graphs	2024	VLDB	5.093636e-05
11,221	Mixed Covers of Keys and Functional Dependencies for Maintaining the Integrity of Data under Updates	2024	VLDB	5.093636e-05
11,227	Extending Graph Rules with Oracles	2024	VLDB	5.093636e-05
11,410	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	5.093636e-05
11,567	PGE: Robust Product Graph Embedding Learning for Error Detection	2022	VLDB	5.093636e-05
11,654	Temporal Dependencies for Graphs	2021	SIGMOD	5.093636e-05
11,659	GRIP: Constraint-based Explanation of Missing Answers for Graph Queries	2021	SIGMOD	5.093636e-05
11,678	Structural Generalizability: The Case of Similarity Search	2021	SIGMOD	5.093636e-05
11,688	Logical Schema Design that Quantifies Update Inefficiency and Join Efficiency	2021	SIGMOD	5.093636e-05
11,727	GEDet: Detecting Erroneous Nodes with A Few Examples	2021	VLDB	5.093636e-05
11,854	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD	5.093636e-05
11,910	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	5.093636e-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
319	Declarative Information Extraction Using Datalog with Embedded Extraction Predicates	2007	VLDB	0.00021377065
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017413839
1,036	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012499878
1,552	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.00010379532
1,671	A Normal Form for XML Documents	2002	PODS	0.00010043595
2,398	BigDansing: A System for Big Data Cleansing	2015	SIGMOD	8.631172e-05
2,539	Minimal MapReduce Algorithms	2013	SIGMOD	8.4526595e-05
3,008	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.8578871e-05
3,251	Keys for Graphs	2015	VLDB	7.5963955e-05
5,878	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	6.0539311e-05
6,029	DREAM: Distributed RDF Engine with Adaptive Query Planner and Minimal Communication	2015	VLDB	6.0014798e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,365	Extending Graph Patterns with Conditions	2020	SIGMOD
2	8,113	Capturing Associations in Graphs	2020	VLDB
3	7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
4	6,639	Propagating Functional Dependencies with Conditions	2008	VLDB
5	1,033	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB
6	11,910	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD
7	10,848	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
8	2,324	Dependencies for Graphs	2017	PODS
9	2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
10	7,099	Discovering Graph Functional Dependencies	2018	SIGMOD