Graph-Based Data Lineage Tracking

42 concepts37 papers1 proposal

When working with complex data pipelines, machine learning models, or collaborative datasets, we rarely deal with static entities. Instead, data evolves: it is filtered, split, merged, transformed by scripts, and used to train models that are themselves fine-tuned over time. Traditional logging mechanisms—such as flat text files or sequential version numbers—fail to capture the causal relationships inherent in this evolution. If a model outputs an unexpected prediction, or a dataset exhibits a sudden anomaly, a flat log cannot easily answer why or how that state was reached.

To solve this, a powerful paradigm has emerged: representing the history, ancestry, and lifecycle of data as a directed graph. By mapping data evolution into a graph structure, we gain the ability to perform structural queries, trace dependencies bidirectionally, and visualize complex non-linear workflows intuitively.

The Anatomy of a Provenance Graph

At its core, graph-based lineage tracking works by translating sequential operations or code execution into a directed acyclic graph (DAG) or a knowledge graph. In this representation, the choice of what constitutes a node and an edge determines the granularity of the tracking:

  • Nodes typically represent discrete states of data, model checkpoints, or specific artifacts.
  • Edges represent the transformations, derivation methods, or human decisions that transition an artifact from one state to another.

For example, data wrangling code can be highly non-linear, involving table joins and splits that obscure the origin of specific data points. As Kai Xiong et al. demonstrate in Visualizing the Scripts of Data Wrangling with SOMNUS, parsing these scripts into a provenance graph allows users to see exactly where data streams converge or diverge, making the logic of the transformation immediately inspectable. This structural abstraction is equally effective in real-time conversational data analysis. In WaitGPT: Monitoring and Steering Conversational LLM Agent in Data Analysis with On-the-Fly Code Visualization, Liwenhan Xie et al. break down LLM-generated code into visual "operation chains," separating data states from transformation operations so users can monitor and steer the analysis mid-conversation.

Beyond raw data, this node-edge mapping scales to entire machine learning ecosystems. As Joseph E. Gonzalez frames it in Letter from the Special Issue Editor, managing the machine learning lifecycle requires graph-based models that explicitly link data subsets, transformation scripts, and final model outputs. This exact mechanism is implemented by Wei Hao et al. in MGit: A Model Versioning and Management System, where nodes signify specific model states and edges define derivation methods like fine-tuning, enabling rapid debugging and automated downstream updates.

Data science is rarely a straight line; it is a collaborative, iterative process filled with alternative hypotheses and branching paths. Graph structures are uniquely suited to handle this non-linear workflow because they can represent concurrent versions and decision points without duplicating the underlying data unnecessarily.

In collaborative environments, teams frequently branch and merge datasets. Anant Bhardwaj et al. show in Collaborative Data Analytics with DataHub how a version graph can track datasets from their raw to processed states, allowing users to inspect changes across divergent histories. To make these operations computationally efficient at the database layer, Michael E. Maddox et al. introduced a dedicated versioning API in Decibel: The Relational Dataset Branching System, enabling Git-like branching and merging directly on relational data.

This graph-based approach also exposes the "hidden" side of scientific research—the myriad of small, analytical choices made during data analysis. Yang Liu 0136 et al. formalize this in Paths Explored, Paths Omitted, Paths Obscured: Decision Points & Selective Reporting in End-to-End Data Analysis by using analytic decision graphs to map out alternative analysis paths and document the rationales behind them. By making the branching nature of research explicit, node-link diagrams—such as those proposed by Alex Kale et al. in Decision-Making Under Uncertainty in Research Synthesis: Designing for the Garden of Forking Paths—allow researchers to communicate the uncertainty and alternative trajectories of their findings.

[Raw Data] ───> [Transformation A] ───> [Dataset V1] ───> [Model Train] ───> [Model Checkpoint]
                     │
                     └───> [Transformation B] ───> [Dataset V2 (Alternative Branch)]

Auditing and Governance via Path Traversal

Why go through the trouble of structuring lineage as a graph? The primary computational advantage is that it turns governance, compliance, and security into graph traversal problems. Because the graph preserves causal directionality, systems can perform path-based queries to trace data upstream to its ancestors (for data auditing) or downstream to its descendants (for impact analysis).

This structural property is vital for security and privacy. In Securing Provenance, Uri Braun et al. point out that the sensitivity of an object's history often differs from the object itself. A graph structure allows for path-based queries that traverse causal links upward or downward, enabling users to audit the history of an asset without gaining unauthorized access to the actual content of intermediate nodes.

Furthermore, graphs serve as a bridge between technical execution and high-level policy compliance. Rui Zhao demonstrates in An Automated Framework for Supporting Data-Governance Rule Compliance in Decentralized MIMO Contexts that data flow graphs can act as a common representation to automate compliance checks, directly linking technical execution traces to governance rules. When applied to AI accountability, Milan Markovic et al. show in The Accountability Fabric: A Suite of Semantic Tools For Managing AI System Accountability and Audit that moving from static documentation to linked knowledge graphs allows auditors to programmatically query the relationships between human approvals, specific datasets, and final model versions across the entire development lifecycle.

Semantic Integration and Human-in-the-Loop Visualization

For graph-based lineage to work across heterogeneous tools, it must be machine-readable, standardized, and interpretable by human operators. Early foundational work in this space, highlighted by Juliana Freire et al. in the front matter for Introduction, emphasized using Semantic Web structures to organize complex data histories, mapping abstract relationships into intuitive visual representations that support human decision-making.

Modern platforms achieve this by unifying code, data, and environments into a single semantic fabric. In Renku: a platform for sustainable data science, Rok Roskar et al. employ an RDF-based knowledge graph to automatically track the lineage of research artifacts throughout their lifecycle. Similarly, Mike Cafarella et al. treat the entire data production lifecycle as a queryable graph in Infrastructure for Rapid Open Knowledge Network Development, storing processing code alongside the data it generates to ensure transparency across collaborative environments.

Finally, these graphs serve as interactive maps for users navigating complex data landscapes. In transcriptomics, Qin Zhu et al. implement a visual 'Data Map' interface in PIVOT: platform for interactive analysis and visualization of transcriptomics data to facilitate easy navigation, version control, and automated re-analysis of derived datasets. To prevent users from losing context during deep data discovery, Houssem Ben Lahmar et al. introduce a dual-tracking mechanism in Provenance-Based Visual Data Exploration with EVLIN that integrates data provenance with the history of user interactions, maintaining logical and visual continuity across exploration steps.

Key Foundational Work

Introduction (2009) — contributed 1 concept elements to this direction.
Using Web Data Provenance for Quality Assessment (2009) — contributed 1 concept elements to this direction.
Provenance and Linked Data in Biological Data Webs (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_provenance_tracking_541e33bd,
  title = {graph-based provenance tracking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-provenance-tracking/rdr_541e33bd79e0439aa7038f1f8543c13f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_based_provenance_tracking_541e33bd_v1,
  title = {graph-based provenance tracking},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-provenance-tracking/rdr_541e33bd79e0439aa7038f1f8543c13f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake