FastGFDs: Graph Data Quality at Scale on a Laptop

Graph Functional Dependencies (GFDs) capture both topological structures in graphs and functional dependencies between attributes. Verifying whether a GFD holds over a graph is computationally expensive — locating suitable subgraphs accounts for about 99% of total runtime.

The original parallel scheme targeted HPC clusters. FastGFDs opens GFD validation to consumer-class PCs with a sequential algorithm that employs Core-First Decomposition and a Compact Path Index (CPI).

The result: 2.6x average speedup over the parallel scheme, 5x memory reduction, and the first open-source implementation available.

What Are Graph Functional Dependencies?

Traditional functional dependencies (FDs) apply to tables:

Employee table:
┌─────┬──────────┬─────────┬──────────┐
│ ID  │ Name     │ Dept    │ Manager  │
├─────┼──────────┼─────────┼──────────┤
│ 1   │ Alice    │ Sales   │ Bob      │
│ 2   │ Charlie  │ Sales   │ Bob      │
│ 3   │ Diana    │ HR      │ Eve      │
└─────┴──────────┴─────────┴──────────┘

FD: Dept → Manager
(Each department has exactly one manager)

Graph Functional Dependencies extend this to graph structures:

Organisation graph:
  Alice ──[works_in]──► Sales ──[managed_by]──► Bob
  Charlie ──[works_in]──► Sales ──[managed_by]──► Bob
  Diana ──[works_in]──► HR ──[managed_by]──► Eve

GFD: (works_in → managed_by)
(If two employees work in the same department, they have the same manager)

GFD syntax:

(X → Y) [pattern]

Where:

• X, Y are attribute sets
• pattern is a graph pattern that defines the scope

Example GFD:

(name → email) [Person(name, email)]
(Each person name maps to exactly one email)

The GFD Validation Problem

Given a graph G and a GFD φ, does G satisfy φ?

Algorithm:
1. Find all subgraphs matching the pattern
2. For each subgraph, check if X → Y holds
3. If any violation found, return FALSE
4. If all subgraphs pass, return TRUE

The bottleneck: Step 1 — subgraph matching is NP-complete in the general case.

For a graph with 1M nodes and a pattern with 5 nodes:

• Naive approach: Check all 5-node combinations → O(n^5)
• Parallel scheme: Distribute across HPC cluster → expensive
• FastGFDs: Core-First Decomposition + CPI → consumer hardware

FastGFDs' Solution

1. Core-First Decomposition

Instead of matching the entire pattern at once, decompose it into core subgraphs:

Pattern: A ──[r1]──► B ──[r2]──► C ──[r3]──► D

Decomposition:
  Core 1: A ──[r1]──► B (find all A-B pairs)
  Core 2: B ──[r2]──► C (extend from Core 1)
  Core 3: C ──[r3]──► D (extend from Core 2)

Advantage: Smaller subproblems, incremental extension, early pruning.

2. Compact Path Index (CPI)

Build an index on path signatures rather than full subgraphs:

Path: A ──[r1]──► B ──[r2]──► C

Index entry:
  Signature: hash(r1, r2)
  Start node: A
  End node: C
  Intermediate: B

Query: Find all paths matching A ──[r1]──► B ──[r2]──► C
Lookup: CPI[hash(r1, r2)] → [A1→C1, A2→C2, ...]
Verify: Check intermediate nodes match

Advantage: Index is compact (path signatures, not full subgraphs), fast lookup.

3. Sequential Optimisation

The parallel scheme was designed for cluster environments with:

• High network latency
• Distributed memory
• Complex coordination

FastGFDs is designed for single-node environments with:

• Low memory latency
• Shared memory
• Simple coordination

Key insight: Parallelism adds overhead. For consumer hardware, optimised sequential beats naive parallel.

What the Benchmarks Say

FastGFDs was evaluated on real-life graphs:

Graph	Nodes	Edges	Parallel Scheme	FastGFDs	Speedup	Memory Reduction
DBLP	2.3M	11.5M	45 min	18 min	2.5x	4.8x
IMDb	4.1M	23.7M	92 min	35 min	2.6x	5.2x
Social	8.7M	142M	187 min	71 min	2.6x	5.0x

Average results:

• Speedup: 2.6x over parallel scheme
• Memory: 5x reduction
• Scalability: Linear up to 100M edges

Key finding: On consumer hardware (16GB RAM, 8-core CPU), FastGFDs validates GFDs on 10M-node graphs in under 2 hours.

Using the Desbordante Implementation

FastGFDs is implemented in Desbordante, an open-source data profiler:

# Install Desbordante
pip install desbordante

# Validate GFDs on a graph
from desbordante import GFDValidator

validator = GFDValidator(
    graph="neo4j://localhost:7687",
    algorithm="fastgfds"
)

# Define GFD
gfd = {
    "pattern": "(Person:name) → (Person:email)",
    "scope": "Person"
}

# Validate
result = validator.validate(gfd)
print(f"Satisfied: {result.satisfied}")
print(f"Violations: {result.violations}")

Python API:

from desbordante.gfd import FastGFDs

# Load graph
graph = Graph.load("graph.csv")

# Define GFD
gfd = GraphFunctionalDependency(
    lhs=["name"],
    rhs=["email"],
    pattern=PersonPattern()
)

# Validate
validator = FastGFDs(graph)
violations = validator.find_violations(gfd)

for v in violations:
    print(f"Violation: {v.nodes}")

Cypher integration (Neo4j):

// Find GFD violations using FastGFDs logic
MATCH (p1:Person {name: $name})
MATCH (p2:Person {name: $name})
WHERE p1.email <> p2.email
RETURN p1, p2

Production Considerations

Graph Size Limits

FastGFDs scales to consumer hardware limits:

Hardware	Max Graph Size	Validation Time
8GB RAM	1M nodes	~30 min
16GB RAM	10M nodes	~2 hours
32GB RAM	50M nodes	~6 hours
64GB RAM	100M nodes	~12 hours

For larger graphs:

• Sample validation: Validate on random samples
• Incremental validation: Validate changed subgraphs
• Distributed FastGFDs: Future work (not yet available)

GFD Design Patterns

Common GFDs for data quality:

# 1. Entity uniqueness
(name, department) → employee_id
[Employee(name, department, employee_id)]

# 2. Referential integrity
manager_id → exists(Employee)
[Employee(manager_id)]

# 3. Attribute consistency
product_id → price
[Product(product_id, price)]

# 4. Structural constraints
supervisor → count(< 3)
[Employee ──[supervises]──► Employee]

Integration with Data Pipelines

class DataQualityPipeline:
    def __init__(self, graph_store):
        self.graph = graph_store
        self.validator = FastGFDs(graph_store)
        self.gfd_constraints = []
    
    def add_gfd_constraint(self, gfd):
        """Register GFD as data quality constraint"""
        self.gfd_constraints.append(gfd)
    
    def validate_on_insert(self, new_nodes):
        """Validate new data before committing"""
        for gfd in self.gfd_constraints:
            violations = self.validator.check_incremental(gfd, new_nodes)
            if violations:
                raise DataQualityError(violations)
    
    def audit(self):
        """Full validation of existing data"""
        results = {}
        for gfd in self.gfd_constraints:
            result = self.validator.validate(gfd)
            results[gfd.name] = result
        return results

Where the Field Is Heading

FastGFDs reveals three trends:

1. Data Quality as Graph Problem

GFDs generalise traditional data quality rules to graph structures. Future systems will treat data quality as graph constraint satisfaction.

2. Consumer-Hardware Feasibility

HPC clusters are no longer required for graph data quality. Optimised sequential algorithms make this accessible to everyone.

3. Open-Source Momentum

The first public implementation lowers the barrier to entry. Expect more tools, more use cases, and better integrations.

The Bottom Line

FastGFDs solves the GFD validation problem by:

• Decomposing patterns into core subgraphs
• Indexing paths with Compact Path Index
• Optimising for single-node execution

For graph data quality, the implication is clear: consumer hardware is enough. HPC clusters are no longer required.

---

Further Reading

• FastGFDs paper: arXiv:2608.02321
• Desbordante: Open-source data profiler (GitHub)
• Graph Functional Dependencies: Original paper (2024)
• ACE-GraphRAG: Context engineering for GraphRAG arXiv:2608.01269