Discovering Graph Functional Dependencies

Summary: Discovering Graph Functional Dependencies (GFDs) for graphs; implication and satisfiability are fixed-parameter tractable, yet validation is co-W[1]-hard. Introduces reduced GFDs and support; scalable parallel discovery and cover computation on large graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5562
Venue: SIGMOD
Year: 2018
Pagerank: 4.9555163e-05
Overall Rank: 6,703 | 53.37%
DOI: 10.1145/3183713.3196916

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,910	Normalizing Property Graphs	2023	VLDB	5.2768691e-05
5,941	Big Graphs: Challenges and Opportunities	2022	VLDB	5.2635446e-05
6,690	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	4.9621556e-05
6,756	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	4.9379361e-05
7,185	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	4.8066159e-05
7,287	Discovering Association Rules from Big Graphs	2022	VLDB	4.7762276e-05
8,133	Towards Event Prediction in Temporal Graphs	2022	VLDB	4.5784634e-05
8,211	Capturing Associations in Graphs	2020	VLDB	4.5581054e-05
8,422	Deducing Certain Fixes to Graphs	2019	VLDB	4.5167705e-05
9,487	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	4.3341665e-05
9,564	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.3254416e-05
10,486	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.1945683e-05
11,001	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.1945683e-05
11,016	Extending Graph Rules with Oracles	2024	VLDB	4.1945683e-05
11,209	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
555	Discovering Denial Constraints	2013	VLDB	0.00020254908
732	Discovering Data Quality Rules	2008	VLDB	0.00017465093
804	YAGO3: A Knowledge Base from Multilingual Wikipedias	2015	CIDR	0.00016463579
1,089	GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.00014157922
2,450	Functional Dependencies for Graphs	2016	SIGMOD	8.7882979e-05
2,527	Dependencies for Graphs	2017	PODS	8.5954406e-05
4,205	Association Rules with Graph Patterns	2015	VLDB	6.3597474e-05
9,564	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.3254416e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,211	Capturing Associations in Graphs	2020	VLDB	4.5581054e-05
2,527	Dependencies for Graphs	2017	PODS	8.5954406e-05
894	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015556428
6,385	Propagating Functional Dependencies with Conditions	2008	VLDB	5.0875028e-05
9,749	Efficient Differential Dependency Discovery	2024	VLDB	4.2897489e-05
25	Dependency Inference (Extended Abstract)	1987	VLDB	0.00083101742
2,058	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS	9.6585264e-05
7,366	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	4.7515248e-05
10,587	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.1945683e-05
2,450	Functional Dependencies for Graphs	2016	SIGMOD	8.7882979e-05