Capturing Associations in Graphs

Summary: Introduces graph association rules (GARs): a pattern+dependency formalism (with ML) to capture regularities, missing links, and inconsistencies in schemaless graphs. Chase-based deduction with Church–Rosser; NP/NP and coNP bounds, DP incremental deduction; parallel algorithms with real/synthetic graph validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h81da9a998e5da755
Venue: VLDB
Year: 2020
Pagerank: 5.3410298e-05
Overall Rank: 8,313 | 44.28%
DOI: 10.14778/3407790.3407795
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beijing Academy of Artificial Intelligence; Shenzhen University; University of Edinburgh)
2. Ruochun Jin (University of Edinburgh)
3. Muyang Liu (University of Edinburgh)
4. Ping Lu (Beijing Academy of Artificial Intelligence)
5. Chao Tian (Alibaba)
6. Jingren Zhou (Alibaba)

BibTeX Citation

@article{fan_vldb20,
        title = {{Capturing Associations in Graphs}},
        author = {Fan, Wenfei and Jin, Ruochun and Liu, Muyang and Lu, Ping and Tian, Chao and Zhou, Jingren},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {11},
        pages = {1863--1876},
        doi = {10.14778/3407790.3407795},
        url = {https://doi.org/10.14778/3407790.3407795},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,496	Big Graphs: Challenges and Opportunities	2022	VLDB	6.0944008e-05
7,318	Discovering Association Rules from Big Graphs	2022	VLDB	5.5411422e-05
8,243	Towards Event Prediction in Temporal Graphs	2022	VLDB	5.3559499e-05
9,769	Explaining GNN-based Recommendations in Logic	2025	VLDB	5.115551e-05
9,847	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1064323e-05
10,390	Detecting Contradictions Within and Across Documents	2027	SIGMOD	4.9605343e-05
10,791	Structural Normalization of Property Graphs	2026	VLDB	4.9605343e-05
11,254	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9605343e-05
11,605	Capturing More Associations by Referencing External Graphs	2024	VLDB	4.9605343e-05
11,618	Extending Graph Rules with Oracles	2024	VLDB	4.9605343e-05
11,676	Graph Association Analyses for Early Drug Discovery	2024	VLDB	4.9605343e-05
11,775	Enriching Recommendation Models with Logic Conditions	2023	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.0006440069
203	AliGraph: A Comprehensive Graph Neural Network Platform	2019	VLDB	0.00025234479
440	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018235529
513	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017023182
696	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014671367
902	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00013142001
952	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012878316
1,046	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012315969
1,090	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012062682
2,269	Dependencies for Graphs	2017	PODS	8.711418e-05
2,894	Functional Dependencies for Graphs	2016	SIGMOD	7.8870146e-05
3,071	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.6670408e-05
3,329	Keys for Graphs	2015	VLDB	7.4086832e-05
4,240	The Interaction between Functional Dependencies and Template Dependencies	1980	SIGMOD	6.7009223e-05
4,420	AliCoCo: Alibaba E-commerce Cognitive Concept Net	2020	SIGMOD	6.5904702e-05
4,838	Association Rules with Graph Patterns	2015	VLDB	6.3753978e-05
5,418	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB	6.1264302e-05
7,263	Discovering Graph Functional Dependencies	2018	SIGMOD	5.5557683e-05
8,420	Deducing Certain Fixes to Graphs	2019	VLDB	5.3198062e-05
9,006	Adding Counting Quantifiers to Graph Patterns	2016	SIGMOD	5.2253856e-05
12,259	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9605343e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,203	Answering Why-questions by Exemplars in Attributed Graphs	2019	SIGMOD
2	7,502	Extending Graph Patterns with Conditions	2020	SIGMOD
3	7,263	Discovering Graph Functional Dependencies	2018	SIGMOD
4	2,269	Dependencies for Graphs	2017	PODS
5	9,847	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD
6	4,838	Association Rules with Graph Patterns	2015	VLDB
7	2,894	Functional Dependencies for Graphs	2016	SIGMOD
8	11,605	Capturing More Associations by Referencing External Graphs	2024	VLDB
9	7,318	Discovering Association Rules from Big Graphs	2022	VLDB
10	11,618	Extending Graph Rules with Oracles	2024	VLDB