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: h3105942671958360
Venue: SIGMOD
Year: 2018
Pagerank: 5.5741839e-05
Overall Rank: 7,245 | 51.31%
DOI: 10.1145/3183713.3196916

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Chunming Hu (Beihang University)
3. Xueli Liu (Harbin Engineering University)
4. Ping Lu (Beihang University)

BibTeX Citation

@inproceedings{fan_sigmod18,
        title = {{Discovering Graph Functional Dependencies}},
        author = {Fan, Wenfei and Hu, Chunming and Liu, Xueli and Lu, Ping},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196916},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196916},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,516	Big Graphs: Challenges and Opportunities	2022	VLDB	6.0957673e-05
5,800	Normalizing Property Graphs	2023	VLDB	5.9876984e-05
6,528	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.7540798e-05
6,860	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6615714e-05
7,228	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5783924e-05
7,345	Discovering Association Rules from Big Graphs	2022	VLDB	5.5453863e-05
8,225	Towards Event Prediction in Temporal Graphs	2022	VLDB	5.3737187e-05
8,299	Capturing Associations in Graphs	2020	VLDB	5.3587491e-05
8,403	Deducing Certain Fixes to Graphs	2019	VLDB	5.3374114e-05
9,813	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1233734e-05
11,195	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9769913e-05
11,556	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.9769913e-05
11,569	Extending Graph Rules with Oracles	2024	VLDB	4.9769913e-05
11,730	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	4.9769913e-05
12,216	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9769913e-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
350	Discovering Denial Constraints	2013	VLDB	0.00020244085
650	Discovering Data Quality Rules	2008	VLDB	0.00015142855
1,027	GraMI: Frequent Subgraph and Pattern Mining in a Single Large Graph	2014	VLDB	0.00012416665
1,043	YAGO3: A Knowledge Base from Multilingual Wikipedias	2015	CIDR	0.00012331034
2,365	Dependencies for Graphs	2017	PODS	8.5625389e-05
3,027	Functional Dependencies for Graphs	2016	SIGMOD	7.7351194e-05
4,860	Association Rules with Graph Patterns	2015	VLDB	6.3763445e-05
12,216	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9769913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,299	Capturing Associations in Graphs	2020	VLDB
2	2,365	Dependencies for Graphs	2017	PODS
3	603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
4	6,766	Propagating Functional Dependencies with Conditions	2008	VLDB
5	10,110	Efficient Differential Dependency Discovery	2024	VLDB
6	209	Dependency Inference	1987	VLDB
7	2,099	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
8	7,289	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
9	11,262	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB
10	3,027	Functional Dependencies for Graphs	2016	SIGMOD