PaperlayerView exact revision on arXiv

Source-linked AI summary

An Error Taxonomy for Property Graph Data

Valerie Restat, Dominique Hausler, Désirée Bruns, Uta Störl

arXiv:2610.23083v1cs.DB

TL;DR

Graph error concepts are less established than tabular ones, and graph topology and context challenge direct transfer of tabular taxonomies. The paper develops a property-graph error taxonomy and maps it to tabular notions; it finds that some issues are inherently graph-specific and often require context beyond single values. The work provides a basis for error characterization, while leaving detection and repair methods outside its scope.

  • Problem

    Tabular error concepts do not fully capture property-graph structure and context, and a systematic taxonomy and mapping for property-graph errors are missing.

    Source: §1 · p. 1, §5 · p. 12

  • Method

    The paper develops a comprehensive property-graph error taxonomy and maps its error types to corresponding tabular error notions.

    Source: §1 · p. 2, §6 · p. 12

  • Results

    A non-trivial subset of graph data quality issues is inherently graph-specific, and detection and repair often require context beyond single values, from neighborhoods to subgraphs.

    Source: §5 · p. 12

  • Takeaways & Limitations

    The taxonomy and mapping provide a shared vocabulary for characterizing and comparing graph errors and a conceptual foundation for future detection and repair methods.

    Source: §1 · p. 2, §6 · p. 12

    The paper addresses error characterization, not detection or repair methods for graph data.

    Source: §1 · p. 2

Abstract

from arXiv · show

Graph data are increasingly used in applications where relationships and topology matter. Yet, compared to tabular data, the notions of data quality and error types for graphs are less established. Tabular error concepts often fail to capture structural properties and context inherent in graph data, hindering systematic quality assessment in graph-based systems. We focus on property graphs (PGs) in graph databases. PGs are often managed without a prescriptive schema, enabling data insertion without explicit validation, while still exhibiting an implicit schema of recurring structural patterns. Irregularities in these patterns may indicate errors, but their interpretation depends on the surrounding graph context. To address these challenges, we provide a systematic view of errors in graph data by proposing a comprehensive graph-specific taxonomy of error types. To position these errors with respect to established work on tabular data quality, we derive a mapping between graph errors and corresponding error notions in tabular data. This mapping highlights which concepts transfer across data models and where structural properties of graphs introduce fundamentally different challenges requiring extensions. Overall, the taxonomy and mapping provide a shared vocabulary for describing, characterizing, comparing, and studying graph data errors, and they lay the groundwork for future work on error detection and repair in graph data.

1 Introduction

The paper proposes a technology-independent taxonomy for property-graph errors and maps these errors to tabular error notions. The mapping distinguishes transferable concepts from graph-specific structural errors, while the paper limits its scope to error characterization.

1 Introduction

  • The taxonomy addresses errors in property and label values, node and edge existence or connectivity, and larger graph patterns.Property graphs represent entities as nodes and relationships as edges, each carrying labels and properties.Source: §1 · p. 1
  • Recurring structural patterns form an implicit schema, but departures from those patterns indicate possible errors rather than errors by themselves.Interpretation depends on graph context.Source: §1 · p. 1
  • The paper presents a technology-independent taxonomy organized across property, entity, relation, graph, and pattern levels.It builds on levels of occurrence proposed by Oliveira et al..Source: §1 · p. 1
  • The authors systematically relate graph error types to tabular taxonomies, identifying shared concepts and errors unique to either data model.Graph topology and structural context make some error types unmappable to tabular counterparts.Source: §1 · p. 2
  • The work characterizes errors but does not develop graph-data error detection or repair methods.The authors leave those methods for future work.Source: §1 · p. 2

2 Related Work

Prior work offers tabular error taxonomies and graph-quality mechanisms, but the paper identifies a gap: no comprehensive characterization of property-graph errors across structural levels and no systematic mapping to tabular errors.

Error Taxonomies

  • Existing tabular taxonomies organize errors by source, structure, and rule categories, but do not account for graph topology and structural relationships.The paper argues that these taxonomies need systematic reevaluation for graph data.Source: §2 · p. 2

Graph Error Taxonomies

  • A knowledge-graph anomaly taxonomy is limited to RDF, covers few anomaly types, and lacks detailed descriptions and mapping to tabular errors.The taxonomy distinguishes anomalies in entity-based, literal-based, and combined triples.Source: §2 · p. 2

Graph Data Quality

  • Graph-quality surveys emphasize metrics, refinement, and lifecycle management rather than systematic error characterization across graph structural levels.The surveyed work includes RDF quality assessment and knowledge-graph refinement and management.Source: §2 · pp. 2–3

Graph Schema and Constraints

  • Prior graph mechanisms describe, infer, constrain, or normalize structures, but address particular properties or inconsistencies rather than a complete error specification.Examples include schema and key constraints, profiling, and normalization.Source: §2 · p. 3

3 Data Quality Challenges for Graph Data

Graph-data quality assessment must account for flexible schemas, context-dependent missingness, topology, and the possibility that structural irregularities are intentional. These challenges shape how property-graph errors are characterized and mapped to tabular notions.

3.1 Schema Optionality

  • Property-graph schemas can be absent, partial, or explicit, and this flexibility complicates structural expectations and consistency.Representational variation can affect naming, data types, relationships, and entity identity.Source: §3.1 · p. 3

3.2 Missingness Semantics

  • Whether an absent node or edge is an error depends on the setting’s completeness assumptions: under CWA absence means false, while under OWA it means unknown.Missingness cannot be interpreted independently of the underlying world assumption.Source: §3.2 · p. 3

3.3 Topology & Connectivity

  • Small node or edge changes can alter connectivity and other graph structures, so some errors have effects beyond the modified element.Hubs can be particularly vulnerable to changes affecting structurally important nodes.Source: §3.3 · pp. 3–4

3.4 Context

  • Context combines an element’s neighborhood with relevant labels and properties, helping distinguish error indicators from actual errors.Its scope can range from direct neighbors to larger paths or subgraphs, and may include domain knowledge.Source: §3.4 · p. 4

3.5 Heterogeneity

  • Heterogeneity across labels, properties, or patterns may indicate errors, but can also be intentional and require external context to interpret.Irregularity alone does not establish that a graph element is erroneous.Source: §3.5 · p. 4

3.6 Considerations for the Taxonomy Design

  • The taxonomy design must characterize structural errors beyond individual properties, distinguish irregularities from errors, and consider graph context.These challenges also guide mapping graph error types to tabular counterparts.Source: §3.6 · p. 4

4 Error Taxonomy

This section presents a technology-independent taxonomy of property-graph errors across structural levels, focusing on heterogeneity within a graph instance and how graph context and schema optionality shape error types. It maps graph errors to analogous tabular notions where possible, identifying graph-specific errors and tabular quality concepts without direct counterparts in property graphs.

4 Error Taxonomy

  • The taxonomy distinguishes Property, Entity, Relation, Pattern, and Graph errors, assigning each error to the level where its violated condition is most precisely defined.Errors can have consequences across levels, such as an entity error distorting relations, but the taxonomy classifies them by the most precise condition level.Source: §4 · p. 4

4.1 Property-level

  • Property-level errors affect one property key or value, ranging from missing, malformed, invalid, or contextually misplaced values to incorrect, outdated, or anomalous values.Examples include a missing value, a syntax or range violation, and a formally correct value that is false for its entity or relation.Source: §4.1 · pp. 5–6
  • Property keys and graph-wide property patterns can also be erroneous, including missing or misspelled keys, synonymous keys, absent properties, mixed data types, and outdated keys.These types reflect flexibility in property representation; some key-related errors are graph-specific because tabular schemas define columns explicitly.Source: §4.1 · p. 6

4.2 Entity-level

  • Entity-level errors concern existence, identity, or classification, including missing connected entities, missing or incorrect labels, conflicting labels, duplicates, spurious entities, and label-property mismatches.Detecting a missing connected entity relies on graph context and implies one or more missing edges; duplicate entities may be exact or near duplicates.Source: §4.2 · pp. 6–7
  • Entity-level errors also include violations of dependencies between property values, such as a death date preceding a birth date.Source: §4.2 · p. 8
  • Entity-level errors include outdated entities and labels, where stored representations or labels fail to reflect an update or schema rename.For example, after Band is renamed to Group, an older node for the same act may retain the label Band.Source: §4.2 · p. 8

4.3 Relation-level

  • Relation-level errors include missing relations, exact or near duplicates, incorrect edge direction, inadmissible endpoint types, spurious relations, and outdated relations.Missing relations can affect cardinality; direction and endpoint-type violations are graph-specific, while outdated relations map to outdated references.Source: §4.3 · p. 8
  • Outdated relations are mapped to tabular outdated references, while incorrect edge direction, endpoint-type violations, and spurious relations are identified as graph-specific.Direction errors reverse source and target roles; spurious relations require domain context to identify.Source: §4.3 · pp. 8–9

4.4 Pattern-level

  • Pattern-level errors include participation or cardinality violations, cycles where acyclicity is required, broken parent or root structures, and symmetry or inverse-relation violations.These errors concern multi-element configurations; graph cardinality is implicit, and cycles can span heterogeneous node and edge types, unlike the narrower tabular circularity notion.Source: §4.4 · p. 9
  • Pattern-level errors also include duplicate subgraphs, inconsistent statements across subgraphs, and conflated neighborhoods that create false connections, missing relations, and altered connectivity.Duplicate patterns may be exact or partial; conflating nodes can create unintended hubs and change shortest paths.Source: §4.4 · p. 10

4.5 Graph-level

  • Graph-level errors cover systematic bias, excessive non-systematic noise, and syntax inconsistency in how same-type properties are represented across entities.Bias, noise, and syntax inconsistency map respectively to the corresponding tabular error types.Source: §4.5 · pp. 10–11

4.6 Tabular-specific Error Types

  • Some tabular error types have no direct property-graph counterpart, including referential-integrity violations and certain attribute dependencies; domain violations are excluded as standalone graph errors.Tabular circularity is narrower than graph acyclicity, which can span heterogeneous node and edge types; domain rules depend on application-specific patterns and modeling choices.Source: §4.6 · p. 11

5 Discussion

The discussion organizes property-graph errors across five structural levels and explains how schema optionality, heterogeneity, connectivity, dependencies, and versioning shape their characterization. It also identifies graph-specific errors that lack tabular counterparts and notes that some classifications require context beyond individual values.

5 Discussion

  • Graph errors span five structural levels, from property, entity, and relation errors to more complex pattern- and graph-level errors.The taxonomy considers connectivity, context, and schema optionality across these levels.Source: §5 · p. 11
  • Schema optionality can make errors cross-layer, involving schema and data together rather than data alone.Property graphs attach key-value properties to graph elements, alongside schema-relevant labels and edges.Source: §5 · p. 11
  • Heterogeneity can be syntactic, semantic, or structural, and may be intended variation rather than an error, requiring external context for validation.It can occur across all discussed levels, with combined forms complicating detection.Source: §5 · pp. 11–12
  • Connectivity gives graph topology semantics that can span subgraphs or the entire graph, so schema and data dimensions cannot always be characterized separately.In property graphs, labels and property keys attach schema-relevant information directly to graph elements.Source: §5 · p. 12
  • Different normalization levels within one graph can represent the same information, making dependency checks important for finding inconsistent redundant or related values.Such errors may require schema-evolution operations, such as split operations.Source: §5 · p. 12
  • Lazy migration can leave outdated and updated graph versions coexisting, creating temporal irregularities that require external context for reliable classification.Examples include an outdated property key or an outdated entity.Source: §5 · p. 12
  • A subset of graph errors has no tabular counterpart, and graph errors therefore need a structural organization specific to property graphs.The blurred boundary between schema and data and the semantics of graph surroundings contribute to this mismatch.Source: §5 · p. 12
  • A non-trivial subset of data-quality issues is inherently graph-specific, and detection or repair may need context ranging from neighborhoods to subgraphs.Schema optionality and connectivity’s rich semantics are identified as primary reasons.Source: §5 · p. 12

6 Conclusion and Future Work

The paper develops a comprehensive property-graph error taxonomy and maps its error types to corresponding tabular notions. It identifies graph-specific challenges and points to detection and repair as future work.

6 Conclusion and Future Work

  • The paper develops a comprehensive graph-error taxonomy and maps graph errors to corresponding tabular error notions.The mapping connects established tabular concepts to graph-specific characteristics and clarifies which concepts transfer and where distinct challenges arise.Source: §6 · p. 12
  • Future work should develop detection and repair techniques tailored to graph-specific challenges, including schema optionality, structural semantics, and heterogeneous normalization.The paper’s focus is error characterization rather than detection or repair.Source: §6 · p. 12
  • Proposed future directions include constraint- and dependency-based detection and repairs that account for schema evolution and versioning.The versioning example is the coexistence of outdated and updated representations.Source: §6 · p. 12

Declaration on Generative AI

The authors report using ChatGPT (GPT-5.6 Sol) for rephrasing and as a thesaurus.

Declaration on Generative AI

Artifacts

A comprehensive graph covering the property-graph taxonomy’s error types is available on Zenodo.

Artifacts

  • A comprehensive graph encoding all property-graph taxonomy error types is available on Zenodo.The artifact highlights and encodes the error types in alignment with the paper.Source: Artifacts · p. 12

Related papers

Loading 2610.23083v1…