Knowledge Graphs

The task and the information it requires

A knowledge graph connects identifiable entities through relationships with explicit meanings. A connection stating that a talk was presented at a conference carries more information than an undifferentiated link between two strings. Shared identities allow separately collected records to participate in the same query. [2]

Competency questions specify what the knowledge base must answer and at what level of detail. They bound the categories and relationships worth maintaining. This task-first modeling method is developed in Ontology Development 101; intended outcomes provide the corresponding evaluation boundary. [3]

The running task identifies production deployment occurrences whose software inventories contain a path to an exact library release, then identifies their responsible teams. The constructed fixture adapts CycloneDX’s published Acme Application dependency diamond. Releases, deployments, teams and observation records added here are examples, not observations of a production environment. [4]

The expected answer carries evidence as well as names: deployment D1, artifact H1, dependency witness W1 and team Blue, qualified by the deployment observation, ownership source, applicable time and coverage. [5][6]

Entities, identities and modeling granularity

An entity is a distinguishable thing in the modeled domain. A relation specifies a connection between entities. Nodes represent entities; typed, directed edges represent relationships. Properties hold attributes, such as a name or observation date. Relationship direction matters: a deployment uses an artifact, while the artifact does not thereby use the deployment. [11]

A triple is a subject–predicate–object statement. An entity reference identifies something that other statements can also reference; a literal supplies a value, such as text or a typed date. The RDF Primer explains this distinction. A graph schema specifies vocabulary and structural expectations; it does not establish that populated records are true. [12]

A source record describes an entity; a textual mention refers to one. Neither is automatically the entity’s canonical identity. Several records can describe one entity, and one document can mention several entities. Observation identity remains distinct from the domain identities a graph connects. [13]

If H1 contains common-util release 1.0 and H2 contains release 2.0, merging both releases into a library-name node destroys the distinction needed by an exact-release query. Conversely, preserving release identifiers does not establish that an inventory actually describes a deployed artifact; that requires another evidenced connection. [14][15]

Relationships and qualified assertions

Resource Description Framework (RDF) represents information as triples. Internationalized Resource Identifiers, or IRIs, identify resources and predicates. Reusing an identifier connects statements. Serialization formats can change without changing the graph’s logical content; choosing which real-world thing an identifier denotes remains a modeling decision. [12]

An n-ary relation involves several participants or qualifications that belong together. The relation-instance pattern introduces a node for that relationship. Two dependency assertions can share release endpoints while retaining different inventory contexts. Deriving an unqualified dependency edge from those records requires an explicitly chosen mapping. [18]

Reification gives a statement an addressable description. RDF 1.1 uses a statement resource with subject, predicate and object properties. Describing a triple this way does not entail the triple itself, and asserting the triple does not entail its reification. Separate descriptions of the same triple can therefore carry separate attribution without automatically endorsing the relationship. [19]

An RDF dataset has one default graph and may have named graphs. A graph name does not inherently identify its author, authenticate its contents or declare endorsement. The default graph is not automatically their union. Source attribution and inventory scope require explicit application conventions in addition to dataset organization. [20]

Ontology, inference and validation

An ontology describes domain categories, relationships and their meanings. A class is a category; an instance is an individual classified within it. A taxonomy organizes categories hierarchically. An ontology can additionally describe relationship meanings and logical rules, giving multiple ingestion pipelines a shared domain model. [21]

Vocabulary reuse requires comparing definitions and granularity, not merely labels. A superclass must actually include its subclasses. Two systems using the word component might mean a package family and a deployable artifact, respectively; declaring them equivalent would erase a distinction the investigation needs. [3]

An axiom is a statement given logical meaning by the ontology. RDF Schema (RDFS) and the Web Ontology Language (OWL) support type inference: subclass membership propagates upward, and domain/range declarations infer relationship-endpoint types. Under OWL’s open-world assumption, missing information is not automatically false. The OWL Primer explains these semantics. [22]

The Shapes Constraint Language (SHACL) checks selected graph records against declared requirements. A shape can require exactly one artifact reference and a specified endpoint class. Cardinality means the permitted number of values. Validation reports violations; it does not repair the graph or verify the observation. [23]

Transitivity must follow the relation’s meaning. If Sue is an ancestor of Mary and Mary of Anne, an ancestor rule can derive Sue’s relationship to Anne. A two-edge dependency chain similarly supports reachability, but it must not be relabeled as a direct dependency. Different predicates preserve that distinction. [24]

Reasoning strategies depend on permitted constructs. OWL 2 QL supports ontology-guided query rewriting over relational data; OWL 2 RL supports restricted rule-engine implementations. A rule engine sound on arbitrary RDF need not recover every OWL entailment. Choose the required semantics before choosing materialization or query-time reasoning. [25]

Entity resolution across sources

Entity resolution decides which records or mentions describe the same entity. Record linkage connects matching records across sources; entity linking connects a textual mention to an existing entity. Mention recognition locates the referring text, while relation extraction identifies relationships expressed in it. These tasks can share an implementation without becoming the same decision. [13]

Normalization standardizes representations; it does not establish identity. Embedding similarity can propose matches beyond a fixed alias list, but similar names can preserve meaningful distinctions. Duplicates and revisions explains the underlying identity rule; representation failures explains why semantic proximity can miss a decisive difference. [26]

Blocking restricts expensive matching to candidate record pairs. It saves comparisons but can exclude true matches before scoring begins. A candidate generator therefore needs its own coverage assessment. Failure to find a candidate is not evidence that a record describes a new entity. [27]

The Fellegi–Sunter model compares how likely observed field agreement is among matching and nonmatching records. Agreement on a rare value supplies stronger evidence than agreement on a common one. A prior and multiple comparisons contribute to a match weight; correlated fields can overstate evidence if treated as independent. [28]

Use validated decision thresholds and retain an unresolved outcome when evidence is insufficient. Review candidates before creating or merging identities. Preserve source identifiers, comparison evidence and decision versions so mistaken merges can be reversed; restoring identities may also require repairing references rewritten elsewhere. [31][32]

Graph construction and assertion evidence

Structured inventories provide fields and keys that can be mapped directly. Documents require extraction into the chosen model. Schema-guided extraction constrains categories and relationship types, making outputs more consistent. Instructions can also standardize names and units, but prompt compliance remains fallible. [33][34]

R2RML maps relational tables or queries to RDF. An employee row keyed by employee ID can join a department row through department ID and emit an employee-to-department statement. Stable keys and identifier templates preserve identity across display-name changes. The resulting graph may be virtual; mapping does not require a second stored copy. [9]

Existing business entities can guide extraction toward recognition and relationship enrichment. Preserve document and chunk structure so assertions remain connected to their source passages. Evidence spans explain passage location; meaning beyond schema acceptance explains why an accepted structure can still reference the wrong entity. [35][36]

An assertion is a recorded claim. Provenance records its origin and production history. PROV-O distinguishes source entities, transforming activities and responsible agents; its agents can be people, organizations or software. An extracted assertion is a derived artifact, not the original source itself. Lineage connects those artifacts without certifying their truth. [37]

Retain source version and passage locator, transformation identity, resolution decision and review outcome. A source’s participation in an extraction batch does not establish that it contributed to every output. Keep links specific enough to trace the assertion through intermediate representations. [40]

For this application, publication is an explicit gate: accepted assertions enter a coherent snapshot; rejected and unresolved candidates remain available for investigation. A deterministic mapping can still preserve a source error. Construction stages separate source structure, domain extraction and optional enrichment, making the point of failure inspectable. [41]

Time, disagreement and incomplete knowledge

Valid time records when a claim applies in the domain; system time, also called transaction time, records when its version was known to the database. Bitemporal storage retains both. A query selects intervals containing its domain time and knowledge cutoff, using start-inclusive, end-exclusive boundaries. Open ends are unbounded. [1]

Version identity, publication time, retrieval time and generation time answer different questions. A newly generated summary can still describe an old source. Neither its timestamp nor its fluency establishes that ownership remains current. [42]

Source authority is specific to the claim. An organizational registry may determine responsibility while an operational inventory supplies deployment observations. Data owners must clarify field meanings, joins, safeguards and reporting conventions. Import order cannot replace those agreements when sources conflict. [29]

Retraction withdraws support; replacement supplies a successor assertion; supersession records which assertion a policy now prefers. Preserve the evidence responsible for invalidation and retain competing claims when their disagreement remains unresolved. Merging entities must retain both source sets rather than silently discarding one. [43]

In a dependency inventory, an explicitly empty dependency list means none are declared. An omitted dependency entry can mean unknown. Negative answers therefore need a declared collection boundary. [4]

Relationship patterns and result rows

Graph queries match relationship patterns using shared variables, much like joins between tables. Cypher expresses property-graph patterns; relationship names such as WORKS_ON are domain-defined vocabulary, not built-in knowledge. For complex traversals, an expert tool or constrained query template can expose the intended operation without relying on unrestricted model-generated queries. [44][45]

For collaboration questions, matching people through shared projects answers a different question from searching documents for the word collaborator. The relationship’s definition determines what the result means. Shared work can support a project-grounded answer without establishing a broader social relationship. [46]

The fixture’s accepted, time-selected query view admits only production deployments supported by designated deployment observations at most one day old. Inventory graphs hold occurrence dependencies and release mappings; default metadata joins artifacts to inventory roots and deployments to services. Only equally fresh, time-selected ownership from the designated registry is exposed before OPTIONAL; unresolved owners leave qualifying deployments eligible. These eligibility and projection rules are application-defined, not inherent in named graphs. [20][18][29][42]

SPARQL joins shared variables. Here : denotes the fixture vocabulary; + requires at least one dependency hop. SELECT DISTINCT ?d ?team WHERE { ?d :artifact ?a; :service ?s. ?a :inventory ?g; :root ?r. GRAPH ?g { ?r :dependsOn+ ?t. ?t :release :requestedRelease. } OPTIONAL { ?s :owner ?team. } } [47]

SPARQL returns multisets of bindings. Projection can retain duplicates; DISTINCT removes duplicate projected rows. GROUP BY aggregates groups; COUNT(*) counts rows, while COUNT(DISTINCT ?d) counts distinct bound deployments. Fixed path sequences can yield repeated endpoints; arbitrary-length paths test connectivity rather than enumerate alternative routes. Surrounding joins can still duplicate rows. [47]

Traversal boundaries and execution work

A traversal follows selected relationships; a hop crosses one. Direct dependencies are one hop away. Reachability means an eligible path exists; transitive closure records reachable pairs. Breadth-first search expands successive depths, while depth-first search follows a branch before alternatives. Relationship type, direction and stopping boundaries determine the paths explored. [48]

Repetition policy also matters. A walk permits repeated vertices and edges, a trail forbids repeated edges, and a simple path forbids repeated vertices. The investigation returns distinct reachable endpoints with selected witness paths, not every possible walk. Cycles require explicit handling; recursive SQL can track visited identities and detect them. [8]

Key visited state by inventory occurrence, not package name. Preserving scope prevents a traversal from entering one build and leaving through another’s dependency record. Visited suppression supports endpoint reachability, but can discard alternative witnesses; storing every path is a different and potentially much larger task. [48]

An index can locate selective starting nodes without eliminating subsequent expansion. High-degree nodes, joins and late filters can produce many intermediate rows even when the final answer is small. A Cartesian product combines every row on one side with every row on the other. [49]

Planner statistics estimate selectivity and relationship counts; they do not guarantee uniform degree. In Neo4j, EXPLAIN reports estimates without executing, while PROFILE executes and reports actual rows and database hits. Hits describe storage-engine work, not elapsed time or disk reads. PROFILE adds overhead and executes writes if the query writes. [50][51]

A result LIMIT is not a reliable work bound. Define an application contract for depth or work exhaustion: return supported matches, a termination reason and the unresolved frontier. A partial traversal cannot establish that no additional matches exist. Complete enumeration and an honest partial answer are different task outcomes. [8]

A traceable dependency-and-owner result

At day 8, the fixture requests common-util 1.0. Its application contract designates deployment observations for artifact identity and environment, inventories for declared dependencies, and the organizational registry for ownership. Observations must be at most one day old. These authority and freshness rules belong to this application, not to the graph model. [29]

Deployment status describes observed controller state, not every running image identity or application health. A requested image reference likewise does not establish what currently runs. The fixture stipulates an artifact-specific observation; a real system must obtain and retain that evidence. [5][15]

A dependency path identifies a candidate for investigation, not proof that vulnerable code executes or causes an incident. Vulnerability Exploitability eXchange (VEX) communicates whether a vulnerability is exploitable in a particular product context. A VEX assessment requires applicable supporting evidence beyond connectivity. [53]

Search selects relevant items; retrieval-augmented generation supplies evidence to a model producing an answer. GraphRAG names graph-assisted approaches, including semantic search for starting nodes followed by relationship expansion. Graph results can equally serve ordinary application code. [54]

Other GraphRAG approaches build community summaries for corpus-wide questions and combine partial answers from those summaries. The different mechanism serves a different information need. Neither architecture removes extraction errors, and a finite graph does not automatically enforce refusal when evidence is absent. Preserve provenance, uncertainty and coverage at the consumer boundary. [55][56]

Source updates and dependent conclusions

Idempotent ingestion makes replaying the same import leave the accepted state unchanged. A proposed contribution ledger uses a non-null unique key of source ID, immutable source version and canonical assertion ID. Freeze normalization and extraction output for each version; otherwise nondeterministic re-extraction can add new assertions during a supposed replay. [57]

# Application contract; contribution key is unique and non-null.
with database.transaction():
    inserted = insert_contributions(
        frozen_rows,
        on_conflict="DO NOTHING",
        returning="assertion_id",
    )
    for assertion_id, delta in counts(inserted).items():
        increment_support_in_database(assertion_id, delta)

Insertion and counter changes must commit or roll back together. Increment with database arithmetic rather than writing an application-read counter value. Alternatively, count contribution rows directly. Retry the complete transaction after failure. This boundary does not automatically include external graph stores or reasoning services. [58]

Define version activation explicitly: replacement can deactivate an older contribution instead of accumulating every revision. Publish the resulting assertion set and its dependent views coherently; committed source rows alone do not establish that every consumer has caught up. [57][58]

Materialization precomputes logical consequences. Datalog is a rule language; for positive, function-free rules over a finite domain, repeated application reaches a fixed point when no new facts appear. This can move inference work ahead of queries, while creating a corresponding update obligation. [59]

Only source-support zero crossings change the explicit fact set. Logical support is separate: another proof can preserve a conclusion. Nonrecursive maintenance can count derivations; recursive cycles complicate counting. DRed overdeletes potentially affected consequences, then rederives those still supported. [60]

Identity repair and semantic change

A false merge can redirect many assertions to the wrong identity. Wikidata’s unmerge procedure restores earlier revisions and warns that references rewritten elsewhere may also need reversal. Deleting an equivalence link is therefore insufficient when the merge changed records or downstream references. [32]

A bad import should be contained before its outputs spread. Preserve the previous published state, identify the import’s contributions, and revalidate the replacement before publication. Database rollback covers only its transaction; already published derivatives need separate recovery. Verified recovery supplies the broader release discipline. [58]

Changing a relationship definition can change query behavior while records still parse successfully. An ontology-driven retriever can select different edges after an annotation changes. Treat that as a semantic release: preserve old and new definitions, identify affected mappings and queries, and verify their expected results before switching consumers. [62]

Assign source stewards to freshness and coverage, identity reviewers to ambiguous matches, and schema owners to meaning changes. Monitor stale records, dangling references and unresolved work. These responsibilities turn errors into owned decisions rather than indefinitely accumulating exceptions. [29]

Correction and deletion must reach derived artifacts as well as original records. A revision is a new entity with a derivation relationship, preserving the history needed to locate affected outputs. Lifecycle fulfillment covers obligations across stores; graph lineage supplies references for carrying them out. [37]

Graph quality, task usefulness and operating cost

Compare the maintained graph with a reasonable same-source baseline, such as recursive SQL. Give both the same collection, identity mappings, cleanup and permissions. Controlled comparisons isolate the changed mechanism. Reported improvements from an assembled graph-and-generation system do not isolate the contribution of relationships alone. [63]

Historical evaluation must fix the knowledge cutoff across source records and derived features. Selecting a past valid time using today’s corrected knowledge can leak later information. A reproducible past answer and today’s best reconstruction of the past are different evaluation targets. [1]

Resolution evaluation needs explicit populations. Let $U$ contain eligible record pairs, $T\subseteq U$ the true matches, $C\subseteq U$ distinct candidates and $A\subseteq C$ accepted pairs. For deduplicating $n$ records, $|U|=n(n-1)/2$. Deduplicate overlapping blocks before counting candidates. [27]

Candidate precision is $|C\cap T|/|C|$; reduction ratio is $1-|C|/|U|$. The latter measures avoided comparisons, not accuracy. Labels restricted to candidates cannot reveal blocked-out true matches. Report empty denominators as undefined with counts, rather than silently converting them to perfect scores. [27]

Final entities require separate evaluation. Form all unordered pairs within each predicted cluster, including unscored implied pairs. Pairwise precision and recall compare these with reference pairs; exact-cluster precision and recall require recovering entire clusters. Verify record coverage and represent genuinely unmatched records as singletons. Larger clusters contribute more pairs, so pairwise scores can hide poor recovery of small entities. [30]

Retain the graph when supported task improvements justify its ongoing burden. Narrow it when only particular relationship questions benefit. Remove a redundant representation when the baseline satisfies the same requirements more simply. Graph size and ingestion throughput describe activity; they do not establish usefulness. [10]

Open questions

1. 01

   Semantic evolution across organizations remains difficult because identical labels can hide incompatible definitions and granularity. Progress would include versioned mappings that preserve competency-question answers or explicitly identify which answers change when a shared concept is revised. [3]

2. 02

   Confidence across graph proofs remains unresolved when premises share sources or depend on one identity decision. Multiplying edge scores ignores those dependencies and alternative proofs. Progress requires calibrated conclusion-level uncertainty that distinguishes copied evidence, shared failure causes and genuinely independent support. [69][39]

3. 03

   Complete answers under strict online work limits remain costly when facts change frequently. Materialization moves work into maintenance rather than removing it. Progress would demonstrate bounded serving work together with measured refresh lag and correct retraction behavior under realistic update loads. [59]

4. 04

   Corrections across derived stores remain hard because summaries and intermediate answers contain information beyond their citations. Progress would demonstrate that a source correction or permission change reaches every affected report, cached answer and conversation artifact before reuse, with explicit unavailable coverage. [70][71]