Knowledge Graphs

• Graphs provide concise relational abstractions, flexible schema evolution, navigational queries, semantic reasoning, scalable analytics, and direct support for machine learning over diverse data.These capabilities support domains including social data, biological interactions, bibliographic citations, co-authorships, and transport networks.Source: §1 · pp. 1–2
• The paper responds to the lack of a general unifying summary by offering a comprehensive and accessible introduction for researchers and practitioners new to knowledge graphs.Existing tertiary literature typically focuses on specific aspects, whereas this tutorial aims for broad coverage while referring readers to more technically detailed surveys where appropriate.Source: §1 · pp. 2–3
• The tutorial addresses the knowledge-graph lifecycle from schema, identity, and context representation through deductive and inductive knowledge construction, creation, enrichment, quality assessment, refinement, and publication.Schema captures high-level structure, identity links graph or external nodes to the same real-world entity, and context specifies settings in which knowledge is held true.Source: §1 · pp. 2–3
• Knowledge graphs represent real-world entities and their relations as graph-structured data, with knowledge accumulated from external sources or extracted from the graph itself.The paper adopts an inclusive definition that accommodates directed edge-labelled graphs, property graphs, simple statements, and quantified statements represented through ontologies or rules.Source: §1 · p. 2
• Knowledge graphs serve as evolving shared knowledge substrates in open and enterprise settings, supporting applications such as search, recommendations, personal agents, advertising, analytics, risk assessment, and automation.Open examples include DBpedia, Freebase, Wikidata, and YAGO, while enterprise examples span web search, commerce, social networks, and finance.Source: §1 · p. 3
• The paper is organized from graph data models and query languages through schema, identity, context, deductive and inductive methods, graph construction, quality, refinement, publication, applications, and future directions.Appendices provide historical background, previous definitions, and formal definitions used in the main text.Source: §1 · pp. 3–4

2.1 Models

• Graph data models represent knowledge as nodes and edges, avoiding the upfront schema constraints of relational models while supporting incomplete and diverse data integration.Directed edge-labelled graphs permit arbitrary binary relations and represent missing information by omitting edges; RDF standardizes this model with IRIs, literals, and blank nodes.Source: §2.1.1 · pp. 5–6, §2.1 · p. 5

2.1.2 Heterogeneous graphs.

• Heterogeneous graphs assign types to nodes and edges, enabling type-based partitioning for machine learning but typically restricting each node to one type.Edge types distinguish homogeneous from heterogeneous edges, while directed edge-labelled graphs can instead express multiple node types through relations.Source: §2.1.2 · p. 6

2.1.3 Property graphs.

• Property graphs attach labels and property–value pairs to nodes and edges, providing a concise, flexible representation that can be translated to directed edge-labelled graphs without information loss.They are prominently used in graph databases such as Neo4j, whereas directed edge-labelled graphs provide a more minimal model.Source: §2.1.3 · p. 7

2.1.4 Graph dataset.

• Graph datasets organize multiple named graphs plus a default graph, supporting source-specific updates, metadata, provenance, and integration of repeated entities across graphs.This structure is particularly useful for managing Linked Data composed of interlinked RDF graphs on the Web.Source: §2.1.4 · pp. 7–8

2.1.5 Other graph data models.

• Knowledge graphs may use alternative models such as nested graphs or hypergraphs, although the paper primarily discusses directed edge-labelled graphs because of their relative succinctness.Graph storage and indexing range from relational encodings to custom and distributed techniques for efficient access and query evaluation.Source: §2.1.5 · p. 8, §2.1.6 · p. 9

2.2.1 Graph patterns.

• Graph query languages including SPARQL, Cypher, Gremlin, and G-CORE share primitives based on graph patterns, relational operators, and path expressions.Basic graph patterns match variable mappings whose instantiated patterns are contained in the data graph, with homomorphism- and isomorphism-based evaluation semantics adopted by different languages.Source: §2.2 · p. 9, §2.2.1 · p. 9

2.2.2 Complex graph patterns.

• Complex graph patterns combine graph-pattern results with relational operations such as projection, selection, joins, union, difference, and optional matching, supporting conjunctive and first-order queries.Query languages may use bag semantics, which preserve duplicate results, or set semantics, which remove them.Source: §2.2.2 · p. 10

2.2.3 Navigational graph patterns.

• Navigational graph patterns use regular path queries with inverse, repetition, disjunction, and concatenation to search recursively connected nodes, while restricted semantics address cycles and potentially infinite paths.Path queries may return paths or the finite node pairs connected by matching paths, and can be combined with relational operators into complex navigational patterns.Source: §2.2.3 · pp. 10–11

3 SCHEMA, IDENTITY, CONTEXT

• Knowledge graphs extend data graphs with representations of schema, identity, context, ontologies, and/or rules, which may be embedded in or layered above the graph.This part discusses schema and identity; ontologies and rules are deferred to Section 4.Source: §3 · p. 12

3.1 Schema

• Schemas may be semantic, validating, or emergent: they respectively define meanings for reasoning, check existing graph data against constraints, or expose latent structure automatically.Graphs can postpone schema definition, but schemata prescribe high-level structure or semantics when needed.Source: §3.1 · p. 12, §3.1.2 · p. 14, §3.1.3 · p. 16

3.1.1 Semantic schema.

• Semantic schemata encode classes, class hierarchies, property hierarchies, domains, and ranges, enabling inference over graph terms; RDF Schema supports these features for RDF graphs.Semantic schemata commonly use the Open World Assumption for incomplete large-scale data, while Local Closed World assumptions can specify complete portions.Source: §3.1.1 · pp. 12–13

3.1.2 Validating schema.

• Validating schemata specify constraints and report violations, with shapes targeting nodes and restricting property counts, types, relationships, inheritance, and open-versus-closed behavior.In the example, EID16 fails the Event shape because it lacks required start and end properties, while Santiago conforms to City only when the shape is open.Source: §3.1.2 · pp. 14–15

3.1.3 Emergent schema.

• Emergent schemata automatically summarize latent graph structure, often through quotient graphs whose partitions preserve simulation or bisimulation properties and support overview, schema design, indexing, querying, and integration.Bisimilarity preserves forward-directed path matches, while emergent summaries can label partitions by cardinality or high-level type to reduce memory overhead.Source: §3.1.3 · pp. 16–17

3.2 Identity

• Identity ambiguity arises when labels such as Santiago can denote multiple real-world entities; globally unique identifiers and external identity links help disambiguate nodes.Heuristic disambiguation may fail in difficult cases, whereas identity links connect a node to an external source.Source: §3.2 · p. 17

3.2.1 Persistent identifiers.

• Persistent identifiers prevent naming clashes when graphs are merged by uniquely identifying entities; examples include DOIs, ORCID iDs, ISBNs, and Alpha-2 country codes.RDF recommends global Web identifiers for nodes and edge labels, using IRIs for non-information resources such as cities or events.Source: §3.2.1 · pp. 17–18
• Persistent identifiers distinguish entities from webpages, avoiding ambiguity; HTTP IRIs enable Web-based descriptions and links, while PURLs can improve identifier persistence.Wikidata separates entity IRIs from webpage URLs, and PURL services can redirect identifiers when document locations change.Source: §3.2.1 · p. 18

3.2.2 External identity links.

• External identity links ground local entities across graphs using identifying information or owl:sameAs, enabling corresponding nodes and their data to be combined.Without such grounding, merging graphs can create distinct nodes for the same city.Source: §3.2.2 · p. 19

3.2.3 Datatypes; 3.2.4 Lexicalisation.

• Datatypes represent machine-processable values such as date-times as typed literals, while lexical labels, aliases, comments, and language tags help users identify and cross-reference entities.RDF literals cannot have outgoing edges, whereas lexicalised knowledge graphs provide human-interpretable information in multiple languages.Source: §3.2.3 · p. 19, §3.2.4 · pp. 19–20

3.2.5 Existential nodes.

• Existential nodes preserve the existence and shared relationships of unidentified resources, but can complicate graph comparison and motivate canonicalisation through skolemisation.RDF blank nodes support existential nodes and structures such as RDF lists.Source: §3.2.5 · p. 20

3.3 Context

• Context defines the scope in which graph data are held true, including temporal, geographic, and provenance dimensions, and may apply to nodes, edges, or subgraphs.Making context explicit supports interpreting data from different perspectives, such as historical or source-filtered views.Source: §3.3 · pp. 20–21

3.3.1 Direct representation; 3.3.2 Reification.

• Direct representation models context as ordinary data, whereas reification represents an edge as a node or identifier so statements can be made about statements.Time Ontology and PROV Data Model provide interoperable specifications for temporal and provenance context.Source: §3.3.1 · p. 21, §3.3.2 · p. 21

3.3.3 Higher-arity representation.

• Higher-arity representations use named graphs, property-graph attributes, or RDF*, with named graphs most flexible for grouping edges and RDF* unable to pair multiple contextual-value groups without edge identifiers.For presidencies spanning two intervals, RDF* may require an additional node to represent each presidency.Source: §3.3.3 · pp. 21–22, Figure 19 · p. 22

3.3.4 Annotations.

• Annotations define contextual domains and operations for automated reasoning, using meet to intersect compatible conditions and join to union alternative results.Annotated RDF can compute temporal validity, filtering answers with empty intersections and combining non-empty intervals.Source: §3.3.4 · pp. 22–23
• Contextual knowledge repositories assign each subgraph its own context, represented explicitly across dimensions with partially ordered values.This supports selecting and combining subgraphs that are valid at different levels of contextual granularity.Source: §3.3.5 · p. 23

3.3.5 Other contextual frameworks.

• Contextual OLAP organizes knowledge graphs in a multidimensional data cube, supporting “slice-and-dice” selection and “roll-up” aggregation.Individual cells contain knowledge graphs, and operations select knowledge by dimensions or aggregate it at higher levels.Source: §3.3.5 · p. 23

4 DEDUCTIVE KNOWLEDGE

• Ontologies represent knowledge as graphs and formalize complex entailments that support automated reasoning, including improved query answering, classification, and inconsistency detection.The discussion focuses on ontologies while relating them to broader logical frameworks such as First-Order Logic, Datalog, Prolog, and Answer Set Programming.Source: §4 · p. 24

4.1 Ontologies

• Ontology definitions encode conventions about terms and entities, so agreement and consistent adoption improve knowledge-graph consistency and interoperability.Different ontologies can model the same event differently, such as splitting one event into several or retaining multiple venues within one event.Source: §4.1 · pp. 24–25

4.1.1 Interpretations. We as humans may interpret the node

• An interpretation pairs a domain graph with a mapping from data-graph terms to entities and relations, separating graph syntax from the meaning assigned to it.The domain graph and mapping are abstract and need not contain real-world entities or relations.Source: §4.1.1 · p. 25
• CWA, OWA, UNA, and NUNA determine whether unknown relations are false and whether different graph terms must denote different entities, thereby defining valid interpretations.OWL adopts the OWA and NUNA, allowing unknown facts and multiple terms to refer to the same entity or relation type.Source: §4.1.1 · pp. 25–26

4.1.2 Individuals.

• OWL provides axioms for individuals and properties, including identity and difference, negation, inverses, disjointness, relational characteristics, cardinality, keys, and property chains.These features allow graphs to state semantic conditions over entities and relations, with property chains deriving relations from concatenated paths.Source: §4.1.2 · p. 26, §4.1.3 · p. 26

4.1.4 Classes.

• OWL defines classes using equivalence, disjointness, set operators, enumerations, and property restrictions such as value, self, and qualified-cardinality constraints.These constructs can be combined to define more complex classes, such as self-driving taxis.Source: §4.1.4 · p. 28

4.2 Semantics and Entailment

• Ontology axioms impose semantic conditions on interpretations, and these conditions generate entailments such as deriving a nearby relation from a symmetric relation.Each axiom restricts which interpretations satisfy the graph, while ontology features define the conditions associated with those restrictions.Source: §4.2.1 · p. 28, §4.2 · p. 28

4.2.1 Model-theoretic semantics.

• A graph entails another graph exactly when every model of the first is also a model of the second, with additional axioms progressively restricting the set of possible models.Under OWA and NUNA, graphs can have infinitely many models because additional relations may exist and multiple graph nodes may map to one entity.Source: §4.2.1 · p. 28, §4.2.2 · p. 29

4.2.2 Entailment.

• Graph entailment means every model of one graph is also a model of another, establishing that the former graph entails the latter.Source: §4.2.2 · p. 29

4.2.3 If–then vs. if-and-only-if semantics. Consider the graph

• Under if–then semantics, the graphs do not entail each other, whereas if-and-only-if semantics makes them mutually entailing and supports more ontology axioms; OWL generally uses the latter.Source: §4.2.3 · p. 30

4.3 Reasoning

• Reasoning is undecidable for the full set of considered ontological features, so practical algorithms trade completeness, input restrictions, or termination; incomplete reasoning is useful for incomplete data, while restricted complete reasoning suits high-risk domains.Source: §4.3 · p. 30

4.3.1 Rules.

• Rules encode graph-pattern if–then consequences and support materialisation or query rewriting, but OWL 2 RL/RDF rules remain incomplete for negation, existential, universal, and counting features.Source: §4.3.1 · pp. 30–31

4.3.2 Description Logics.

• Description Logics organise individuals, classes, properties, and axioms into decidable fragments with tunable expressivity, but expressive satisfiability-based reasoning can become prohibitively complex for large-scale data.Source: §4.3.2 · p. 32

5 INDUCTIVE KNOWLEDGE

• Inductive knowledge generalizes observed patterns into novel predictions that may be imprecise, while models and predictions together constitute valuable inductive knowledge.The capital-city example yields a confidence of 0.959 from 187/195 cases, yet exceptions such as Vaduz show that predictions are fallible.Source: §5 · p. 33

5.1 Graph Analytics

• Graph analytics derives conclusions about nodes and edges from graph topology, including centrality, community detection, connectivity, node similarity, and path finding.Applications include identifying transport hubs, attraction communities, brittle routes, similar attractions, and shortest paths; many techniques were developed for simpler graph models.Source: §5.1 · pp. 33–34, §5.1.1 · pp. 34–35

5.1.1 Techniques.

• Core graph-analytics techniques target central nodes or edges, densely connected communities, graph resilience and reachability, neighborhood-based similarity, and constrained paths.Path definitions include simple paths, shortest paths, and regular path queries, while graph analytics also draws on graph theory and network analysis.Source: §5.1.1 · pp. 34–35

5.1.2 Frameworks.

• Distributed graph-parallel frameworks compute analytics iteratively through message and aggregation phases, while optional global or mutation steps address limitations of neighbor-only computation.The systolic abstraction maps data-graph nodes and edges to processors and communication links; such frameworks are no more expressive than the incomplete Weisfeiler–Lehman test for distinguishing graph structures.Source: §5.1.2 · p. 35

5.1.3 Analytics on data graphs.

• Analytics on edge-labelled or property graphs can use projection, weighting, transformation, or customization, but the chosen strategy may substantially change results and requires empirical validation.Transformations may be lossy or lossless, with lossless versions introducing nodes to preserve labelled-edge information.Source: §5.1.3 · pp. 36–37

5.1.4 Analytics with queries.

• Queries and analytics can be combined by extracting or transforming graphs for analysis, expressing limited analytics, optimizing query execution, ranking results, or interleaving declarative query and analytical steps.An airline-strike example alternates querying transport routes, computing a strongly connected component, and querying events in unreachable cities.Source: §5.1.4 · p. 37

5.1.5 Analytics with entailment.

• Analytics with entailment remains underexplored because semantically equivalent edges can produce different results for direction-sensitive techniques, motivating semantically invariant analytics.Such analytics would return the same results for graphs containing equivalent inverse and hosts-edge representations, focusing on semantic content rather than only topology.Source: §5.1.5 · pp. 37–38

5.2 Knowledge Graph Embeddings

• Knowledge graph embeddings encode entities and relations as dense, low-dimensional vectors whose scoring functions estimate edge plausibility for machine-learning tasks.Self-supervised training increases plausibility for observed edges and decreases it for corrupted negatives, supporting confidence estimation, link prediction, similarity, duplicate detection, and recommendations.Source: §5.2 · pp. 38–39

5.2.1 Translational models.

• Translational models predict edges by making entity-plus-relation vectors approximate target entities, but TransE struggles with multiple targets and cyclical relations.TransH, TransR, TransD, RotatE, and MuRP address these limitations through relation-specific projections, complex spaces, or hyperbolic spaces.Source: §5.2.1 · pp. 39–40

5.2.2 Tensor decomposition models.

• Tensor decomposition represents graph triples as a sparse three-dimensional tensor whose low-rank factors provide entity and relation embeddings.DistMult [568] uses one entity vector twice and therefore cannot model edge direction, whereas RESCAL, HolE, ComplEx, SimplE, and TuckER [30] modify the decomposition to improve expressivity.Source: §5.2.2 · p. 41
• TuckER [30] currently provides state-of-the-art results on standard knowledge graph embedding benchmarks.Source: §5.2.2 · p. 42

5.2.3 Neural models.

• Neural embedding models replace linear or bilinear plausibility scoring with nonlinear functions, balancing expressivity against parameter count and scalability.HypER [28] avoids ConvE’s artificial two-dimensional wrapping and is reported to outperform ConvE on standard benchmarks [28].Source: §5.2.3 · p. 42

5.2.4 Language models.

• Language-model approaches convert graph structure into node-and-edge-label sequences for word-embedding methods, while KGloVe uses personalised PageRank to identify related nodes.RDF2Vec uses biased random walks or canonically labelled subtrees as “sentences” for word2vec [352].Source: §5.2.4 · pp. 42–43

5.2.5 Entailment-aware models.

• Entailment-aware models jointly learn embeddings and rules, increasing plausibility for rule-supported edges while constraining or penalising inconsistent predictions.KALE supports complex rules with t-norm fuzzy logic, RUGE aligns rule and edge scores, and FSL avoids costly ground-rule generation but supports only simple rules.Source: §5.2.5 · p. 43

5.3 Graph Neural Networks

• Graph neural networks build neural architectures over graph topology and support end-to-end supervised classification, prediction, recommendation, verification, and graph-algorithm replacement.Recursive GNNs update node states from neighbouring features until a fixpoint, then learn transition and output functions from labelled examples to label other nodes.Source: §5.3 · p. 44, §5.3.1 · pp. 44–45

5.3.1 Recursive graph neural networks

• Recursive graph neural networks aggregate information from nodes and their neighborhoods through flexible transition and output functions that can be adapted to graph structure.Adaptations include alternative neighborhoods, multiple edge vectors, edge states and outputs, node-specific parameters, and different aggregation functions.Source: §5.3.1 · p. 45

5.3.2 Convolutional graph neural networks

• Convolutional graph neural networks apply convolution-like transitions over graph neighborhoods, requiring spectral, spatial, or attention-based methods to handle nodes with varying numbers of neighbors.Compared with recursively aggregated RecGNNs, ConvGNNs typically use a fixed number of layers and can apply different kernels at each step.Source: §5.3.2 · pp. 45–46

5.4 Symbolic Learning

• Symbolic learning produces interpretable rules and axioms that support deductive reasoning, expert verification, and predictions for unseen nodes and edges.Unlike numerical embeddings and GNNs, symbolic models explain predictions through logical hypotheses and avoid their out-of-vocabulary limitation.Source: §5.4 · p. 46

5.4.1 Rule mining

• Rule mining seeks rules with high support and confidence from positive and negative edges, while addressing incomplete knowledge graphs through assumptions such as PCA.AMIE searches top-down with refinements, pruning, bounded closed rules, and safe heads; differentiable methods learn variable-length path rules but remain limited to path-like rules.Source: §5.4.1 · pp. 47–49

5.4.2 Axiom mining

• Axiom mining learns logical constraints ranging from class disjointness to general class descriptions by clustering, similarity-based analysis, refinement search, and count-query scoring.Examples include disjointness between DomesticAirport and InternationalAirport and descriptions separating entities using properties such as nearby airports and capital status.Source: §5.4.2 · pp. 49–50

6 CREATION AND ENRICHMENT

• Creation commonly begins with a domain-specific core that is incrementally enriched from additional sources through Agile or pay-as-you-go methods.Human editors can contribute directly or curate extracted knowledge, but cost, error, disagreement, bias, vandalism, licensing, tooling, and cultural challenges limit this approach.Source: §6 · p. 50, §6.1 · p. 50

6.2 Text Sources

• Text-based construction combines preprocessing, named entity recognition, entity linking, and relation extraction to convert corpora into candidate nodes and graph edges.Preprocessing may include tokenisation, POS tagging, dependency parsing, and word-sense disambiguation, selected according to downstream requirements.Source: §6.2 · p. 51, §6.2.1 · p. 51

6.2.1 Pre-processing.

• NER uses supervised, bootstrapping, distant-supervision, or rule-based methods to identify entities, while entity linking resolves aliases and context-dependent mentions to existing graph nodes.Linking ranks candidate nodes using context, priors, or graph centrality, helping distinguish entities such as Rapa Nui, Easter Island, and multiple cities named Santiago.Source: §6.2.2 · p. 51, §6.2.3 · pp. 51–52

6.2.4 Relation Extraction (RE).

• Relation extraction supports closed binary relations, open information extraction, and n-ary relations that preserve contextual details such as time, with extracted relations requiring alignment to graph predicates.Methods include patterns, supervised learning, bootstrapping, distant supervision, frame semantics, and discourse representation approaches; interdependent tasks may also be jointly performed.Source: §6.2.4 · p. 52, §6.2.5 · p. 52

6.3 Markup Sources

• Markup extraction can strip tags and apply text methods or exploit document structure through general wrappers, focused table or list extraction, and form-based Deep Web approaches.Repeated website templates and conventions support extraction, while manually defined wrappers are brittle and semi-automatic or distant-supervision methods can induce reusable wrappers.Source: §6.3 · p. 53, §6.3.1 · p. 53, §6.3.3 · p. 54

6.3.2 Web table extraction.

• Web-table extraction requires table classification, normalization, protagonist identification, and cell, type, and relation extraction, often assisted by distant supervision and specialized site frameworks.Tables may contain layout elements, spans, nested tables, or varied formats that conflict with machine readability.Source: §6.3.2 · p. 54

6.4 Structured Sources

• Structured sources can be mapped precisely into graphs through direct or custom mappings, then materialized with ETL or queried virtually through query rewriting.ETL provides graph-native use but requires update propagation, whereas query rewriting maintains one underlying copy; tree data is typically custom-mapped using standards such as GRDDL or JSON-LD.Source: §6.4 · pp. 54–55, §6.4.1 · pp. 55–56, §6.4.2 · p. 56

6.4.3 Mapping from other knowledge graphs.

• Existing knowledge graphs can supply relevant subgraphs through SPARQL construct queries, but entity and schema alignment may be needed before integration.Sources include DBpedia, LinkedGeoData, Wikidata, YAGO, and BabelNet, with alignment supported by linking tools, external identifiers, or manual work.Source: §6.4.3 · pp. 56–57

6.5.1 Ontology engineering.

• Ontology engineering has evolved from waterfall-style development toward iterative and agile methods for building and maintaining large or changing ontologies.DILIGENT separates local changes from global updates and uses review to authorize propagation; newer methods include XD, MOM, and SAMOD.Source: §6.5.1 · p. 57
• Ontology requirements, expressed through Competency Questions, define intended tasks and can be tested by formalizing expected answers as queries over test data.Ontology Design Patterns additionally provide reusable modelling templates or components, often supported by competency questions and formal definitions.Source: §6.5.1 · pp. 57–58

6.5.2 Ontology learning.

• Ontology learning semi-automatically extracts domain terminology, subclass and hypernym relations, and increasingly expressive axioms from text to validate and extend ontologies.Methods target disjointness, unions, intersections, existential and universal restrictions, and qualified-cardinality restrictions.Source: §6.5.2 · p. 58

7 QUALITY ASSESSMENT

• Quality assessment determines whether a knowledge graph can be reliably used for particular purposes despite incompleteness, duplicates, contradictions, and incorrect statements.Quality is defined as fitness for purpose after creation and enrichment from external sources.Source: §7 · p. 58

7.1 Accuracy

• Accuracy measures whether entities and relations represent real-world phenomena, including syntactic correctness, semantic correctness, and timeliness.Syntactic accuracy can use incorrect-value ratios and validation tools; semantic accuracy can use source comparison or process precision; timeliness compares update frequency with underlying sources.Source: §7.1 · p. 58, §7.1.1 · p. 59, §7.1.3 · p. 59

7.2 Coverage

• Coverage assesses omitted domain-relevant elements through completeness and representativeness, including schema, property, population, linkability, geographic, linguistic, and social dimensions.Completeness can be compared with gold standards or extraction recall, while representativeness can compare graph distributions with known populations or statistical laws.Source: §7.2 · p. 59, §7.2.1 · p. 59, §7.2.2 · pp. 59–60

7.3 Coherency

• Coherency evaluates conformity with formal semantics and schema constraints through consistency and validity, which can be measured by counting logical contradictions or constraint violations.The same cardinality restriction may produce a validity violation without producing an inconsistency when the unique-name assumption is absent.Source: §7.3 · p. 60, §7.3.1 · p. 60, §7.3.2 · p. 60

7.4 Succinctness

• Succinctness concerns relevant, concise, compact, and intelligible representation, covering schema and data conciseness, redundant structures, and human-readable labels.Measures include ratios of domain-relevant elements, redundant-node counts, and the prevalence, uniqueness, language coverage, and descriptive adequacy of labels.Source: §7.4 · p. 60, §7.4.1 · p. 60, §7.4.2 · p. 61

7.5 Other Quality Dimensions

• Quality dimensions are not exhaustive because additional dimensions may be needed for specific domains, applications, or graph data models.The section presents dimensions inherited from broader data-quality work alongside dimensions more particular to knowledge graphs, with metrics measuring quantitative aspects.Source: §7 · p. 58, §7.5 · p. 61

8 REFINEMENT

• Refinement targets improvement of an existing local knowledge graph through semi-automatic completion and correction, rather than extracting or mapping content from external sources into it.External sources may still be used to verify local content.Source: §8 · p. 61

8.1 Completion

• Completion fills missing edges judged correct but absent or unentailed, commonly using link prediction techniques from Statistical Relational Learning.Predicted links may be arbitrary-label general links, type links, or identity links.Source: §8.1 · p. 61

8.1.2 Type-link prediction.

• Type-link prediction reduces prediction to classification over semantic classes using features such as incoming and outgoing edge labels, with graph neural networks also applicable.Type links are especially important because they use one edge label and typically fewer classes than other link types.Source: §8.1.2 · p. 62

8.1.3 Identity-link prediction.

• Identity-link prediction finds nodes denoting the same entity using value and context matchers, then can consolidate their edges after thresholded or confidence-based matching.Blocking, windowing, and multidimensional search reduce the O(n^2) cost of pairwise comparisons.Source: §8.1.3 · p. 62

8.2 Correction

• Correction removes existing incorrect edges through fact validation, which scores edge plausibility, or inconsistency repair, which resolves violations of ontological axioms.Fact validation commonly assigns plausibility or veracity scores between 0 and 1 and may use external reference sources.Source: §8.2 · p. 63, §8.2.1 · p. 63

8.2.1 Fact validation.

• Fact validation compares input edges with external unstructured or structured sources using evidence graphs, classifiers, paths, metapaths, or graph embeddings.Unstructured-source fact finders jointly estimate source trustworthiness and fact plausibility, while structured-source methods search evidential paths or learn edge features.Source: §8.2.1 · pp. 63–64

8.2.2 Inconsistency repairs.

• Inconsistency repair is difficult because one edge may participate in many violations and entailment can require removing every derivation of a conflicting edge.Repairs may be manually selected, automatically computed with minimal hitting sets, or avoided through inconsistency-aware query semantics.Source: §8.2.2 · p. 64

8.3 Other refinement tasks

• Completion and correction primarily address accuracy, coverage, and coherency, while other quality dimensions such as succinctness remain possible refinement targets.These two tasks have received most attention to date.Source: §8.3 · p. 64

9.1.1 FAIR Principles.

• FAIR publication targets findability, accessibility, interoperability, and reusability through persistent identifiers, rich metadata, standard protocols, shared vocabularies, links, licenses, provenance, and community standards.Examples include IRIs, VoID, DataHub, ontologies, and the PROV Data Model; Open PHACTS and UniProt are cited as FAIR knowledge graphs with RDF views.Source: §9.1.1 · pp. 65–66

9.1.2 Linked Data Principles.

• Linked Data Principles publish graph-structured data using HTTP IRIs, standard representations, and links between related entities, forming an interlinked Web of Data that machines can retrieve and combine.A central challenge is link discovery across graphs with disjoint nodes, differing vocabularies, and often no existing cross-graph links; manual linkage rules and standard identifiers can help.Source: §9.1.2 · pp. 66–67

9.2 Access Protocols

• Access protocols range from full dumps to complex graph-pattern queries: simpler interfaces reduce server computation, whereas more specific requests reduce bandwidth.Servers may provide multiple complementary protocols for agents with different requirements.Source: §9.2 · p. 68, §9.2.5 · p. 70, Figure 37

9.2.1 Dumps.

• Dumps suit agents needing a complete local copy and can use standard serialization, compression, graph-specific indexes, and update diffs, but they transfer irrelevant data for selective use cases.Property graphs currently lack standard dump syntaxes in the supplied passage, while RDF has standard XML, JSON, and custom syntaxes.Source: §9.2.1 · p. 68

9.2.2 Node lookups.

• Node lookups are inexpensive and support HTTP dereferencing, but traversals may require starting nodes, return irrelevant data, and fail to efficiently answer patterns without suitable incoming-edge access.They can support graph-pattern evaluation by traversing from node to node, but clients may still need to retrieve and inspect excessive data.Source: §9.2.2 · pp. 68–69

9.2.3 Edge patterns.

• Edge-pattern protocols offer more flexible requests with relatively predictable server costs, but may transfer irrelevant intermediate results and make efficient joins dependent on graph statistics or batching extensions.Complex graph-pattern protocols return only final solutions and reduce bandwidth, but require harder-to-predict server computation; SPARQL services can suffer downtimes, timeouts, partial results, and slow performance despite handling millions of requests per day.Source: §9.2.3 · p. 69, §9.2.4 · p. 69

9.3 Usage Control

• Publication may require usage control for licensing, privacy, encrypted personal information, and anonymised sharing, with ODRL representing machine-readable permissions, duties, and prohibitions within graphs.ODRL can model Apache, Creative Commons, and BSD licenses, while compatibility and composition techniques support combining differently governed graphs.Source: §9.3 · p. 70, §9.3.1 · p. 70

9.3.2 Usage policies.

• Access-control policies based on edge patterns can restrict access to selected parts of a knowledge graph.Source: §9.3.2 · p. 70
• Usage policies specify how data may be processed, by whom, and for what purpose, enabling verification against legal norms and subject consent.Proposed vocabularies include those from the SPECIAL H2020 project and the W3C DPVCG.Source: §9.3.2 · p. 71

9.3.3 Encryption.

• Encryption can restrict access to graph nodes, edge labels, or patterns through distinct keys, while functional encryption and specialised indexing avoid decrypting every edge during retrieval.CryptOntology can record the encryption mechanism, but edge decryption may otherwise be inefficient; functional encryption with specialised indexing offers an alternative.Source: §9.3.3 · p. 71

9.3.4 Anonymisation.

• Graph anonymisation suppresses or generalises quasi-identifiers, but neighbourhood and structural attacks motivate stronger guarantees such as k-degree anonymity, k-isomorphic neighbour anonymity, and k-automorphism.These guarantees progressively address attackers with knowledge of node degree, neighbourhood structure, or broader graph structure, and have been adapted to directed edge-labelled RDF graphs.Source: §9.3.4 · p. 72
• Privacy can also be protected at query time with ε-differential privacy, and the appropriate method depends on whether the graph is published as a dump or exposed through a query interface.Stronger privacy guarantees require information loss; k-anonymity suits complete dumps, l-diversity protects groups, and ε-differential privacy is more suitable for query interfaces.Source: §9.3.4 · p. 73

10.1 Open Knowledge Graphs

• Open knowledge graphs commonly follow Open Data and Linked Data principles, use RDF, and provide access through dumps, node lookups, SPARQL graph patterns, and sometimes Triple Pattern Fragments.Prominent examples include DBpedia, YAGO, Freebase, and Wikidata, which cover multiple domains and diverse entities and relationships.Source: §10.1 · p. 73

10.1.1 DBpedia.

• DBpedia extracts multilingual, multidomain Wikipedia knowledge, enriches it with external resources, supports multiple classification schemata, and synchronizes with changing Wikipedia articles.Its extraction framework includes source abstractions, parsers, storage and serialization components, managers, and specialized extractors for diverse Wikipedia content.Source: §10.1.1 · pp. 73–74

10.1.2 Yet Another Great Ontology.

• YAGO combines Wikipedia and WordNet to achieve broad coverage and quality, using an RDFS vocabulary, canonicalization, type checking, reification, n-ary relations, and data types.Later extensions added spatio-temporal context and multilingual Wikipedias.Source: §10.1.2 · p. 74

10.1.3 Freebase.

• Freebase [54] used human contributions, a scalable versioned store, media storage, MQL querying, and loose typing that permitted incompatible structures; its over three billion edges later informed Google’s Knowledge Graph and Wikidata.Freebase became read-only in March 2015, after which much of its content migrated to Wikidata.Source: §10.1.3 · p. 74

10.1.4 Wikidata.

• Wikidata centralizes collaboratively edited, multilingual claims for reuse across Wikipedia and other clients, while supporting references, contradictory viewpoints, schema editing, multiple access protocols, and broad adoption.Its language-agnostic Qxx and Pxx identifiers connect claims to labels, aliases, and descriptions in different languages.Source: §10.1.4 · p. 75

10.1.5 Other open cross-domain knowledge graphs.

• Other open knowledge graphs target lexical, commonsense, and web-extracted knowledge: BabelNet integrates multilingual lexical resources, Cyc encodes common sense, and NELL extracted 120 million edges.Open graphs also cover media, government, publications, geography, life sciences, user-generated content, cultural heritage, music, law, theology, and tourism, supporting integration, recommendation, transparency, archiving, and related applications.Source: §10.1.5 · p. 75, §10.1.6 · p. 75

10.2 Enterprise Knowledge Graphs

• Enterprise knowledge graphs integrate internal and external sources at million- or billion-node scale, refine entities and links, remain up-to-date, combine ontological and machine-learning representations, and often use lightweight taxonomies.Companies deploy them for search, recommendations, conversational agents, advertising, analytics, research, risk assessment, news tracking, and transport automation.Source: §10.2 · p. 76

10.2.1 Web search.

• Enterprise knowledge graphs support applications across search, commerce, social networking, finance, health-care, transport, and oil and gas, including knowledge panels, recommendations, advertising, financial analytics, drug discovery, automation, and risk mitigation.Source: §10.2.1 · p. 76, §10.2.2 · p. 76, §10.2.3 · p. 77

• The paper surveys knowledge graphs from graph-based data models through schema, identity, context, knowledge techniques, lifecycle methods, publication standards, and real-world adoption.Knowledge graphs are defined as graphs of data whose nodes represent entities and edges represent relations intended to convey real-world knowledge.Source: §11 · p. 77

Future directions

• Future research can combine graph databases, knowledge representation, logic, machine learning, graph algorithms, ontology engineering, data quality, natural language processing, information extraction, privacy, and security.The shared objective is maximising knowledge and value distilled from diverse large-scale sources through graph-based data abstraction.Source: §11 · pp. 77–78
• Promising intersections include semantic and contextual reasoning, similarity-based query relaxation, shape induction, contextual embeddings, entailment-aware embeddings, expressive graph neural networks, and rule or axiom mining.These directions connect data graphs with deductive knowledge, inductive knowledge, or both, including formal semantics for property graphs, contextual reasoning, approximate query answers, shape induction, contextual embeddings [282], entailment-aware embeddings, expressive graph neural networks, and rule or axiom mining.Source: §11 · p. 78
• Knowledge graphs will continue maturing along scalability, quality, diversity, dynamicity, and usability dimensions rather than fully solving these challenges.These challenges include scalable deductive and inductive reasoning, reliable data and induced models, contextual or multimodal data, temporal or streaming data, and usability for broader adoption.Source: §11 · p. 78

• The section traces the historical context that paved the way for modern knowledge graphs and surveys definitions proposed before and after the Google Knowledge Graph.Source: A BACKGROUND · p. 108
• Its discussion builds upon, but does not subsume, earlier treatments by Ehrlinger and Wöß and Bergman.Source: A BACKGROUND · p. 108
• Although intended to be comprehensive, the section cautions that its historical references are not exhaustive.Source: A BACKGROUND · p. 108

A.1 Historical Perspective

• Knowledge-graph antecedents include diagrammatic systems developed from Aristotle through Euler and Venn diagrams to formal systems by Sylvester (1878), Peirce (1878), and Frege (1879).Source: §A.1 · p. 108
• Early computational work represented natural language, information, and knowledge, while frames, semantic networks, and conceptual graphs integrated graph representations with formal semantics despite limited resources and semantic challenges.Source: §A.1 · p. 108
• The foundational agenda combined graph-based visual representation, algorithms for formal reasoning, logical and statistical reasoning, and multimodal knowledge sources such as images and sound.Source: §A.1 · p. 108
• Description Logics provided decidable formal semantics for earlier graph notions and underpinned OWL, while RDF, RDFS, SPARQL, Linked Data, and related standards shaped the Semantic Web and later knowledge graphs.Source: §A.1 · pp. 108–109

Origins in the 1970s

• The earliest relevant usage was Schneider’s (1973) instructional knowledge graph, a directed graph of concepts and prerequisite dependencies, alongside related educational and linguistic formulations.Marchi and Miguel (1974) studied high-payoff paths through instructional knowledge units, while Kümmel (1973) represented meaningful symbols as graph nodes.Source: §A.2 · p. 109

Developments in the 1980s

• During the 1980s, knowledge graphs represented medical knowledge, causal text content, part-of and instantiation relations, knowledge-base facts and rules, and software-project entities, often using fixed relation types.Rada (1986) refined weighted medical knowledge through gradual learning, while other works introduced visualization and graph partitioning for modularization.Source: §A.2 · p. 109

Developments in the 1990s

• In the 1990s, knowledge graphs supported symbolic learning, fuzzy and–or dependencies, expert knowledge acquisition, and Bayesian inference over taxonomies, hypotheses, and observations.The and–or graphs in Machado and Freitas da Rocha (1990) encoded conjunctions and disjunctions of dependency relations.Source: §A.2 · p. 109

Developments before 2012

• During 2002–2010, knowledge graphs encoded goal plans, organizational knowledge flow, confidence-weighted search relations, Wikipedia proximity, explanation knowledge, and general-purpose graph querying.Applications included bottleneck detection, graph querying, entity linking, category retrieval, causal explanation extraction, and abstract-machine querying.Source: §A.2 · p. 110

Cross-cutting characteristics

• Across these independent uses, graphs comprised nodes and relational edges, sometimes with weights, labels, or metadata, while combining expert acquisition, text extraction, symbolic and inductive methods, rules, ontologies, learning, and analytics.Earlier graphs were often small and sourced from experts or text; many encoded prerequisite, causal, conjunctive, disjunctive, or belief-weighted relations, unlike modern million- or billion-node graphs.Source: §A.2 · p. 110

• Google’s 2012 announcement made “knowledge graph” a widely adopted term, but its informal description lacked a technical definition.The announcement described a graph that understands real-world entities and their relationships, while later academic attention created a need for precise characterisation.Source: §A.3 · p. 111
• The literature distinguishes four definition categories: graph-based, knowledge-base-based, technically constrained, and extensional definitions by example.These categories reflect differing attempts to specify structure, semantics, reasoning, scope, or representative instances.Source: §A.3 · pp. 111–112
• Category I models knowledge graphs as directed edge-labelled graphs, binary relations, or triples connecting entities, a definition popularised by knowledge graph embedding research and retained in subsequent work.This representation supports embedding methods but leaves open how knowledge graphs differ from ordinary graphs or graph databases and where “knowledge” enters.Source: §A.3 · p. 111
• Technical definitions add schemas, broad entity and domain coverage, information integration, or reasoning, but may exclude common practices such as Google’s Knowledge Graph and knowledge graph embeddings.Paulheim’s criteria include real-world entities, schemas, arbitrary interrelations, and multiple topical domains, while Ehrlinger and Wöß and Bellomarini et al. emphasise reasoning and derived knowledge.Source: §A.3 · pp. 111–112
• Category IV defines knowledge graphs extensionally through examples such as DBpedia, Google’s Knowledge Graph, Freebase, and YAGO, while enterprise practice describes objects and connections supported by optional schemas and shared formal representations.The enterprise view treats knowledge graphs as shared organizational substrates that enable vocabulary reuse, inference, and fact construction, while acknowledging that definitions may not be necessary conditions.Source: §A.3 · p. 112

B FORMAL DEFINITIONS

• The formal definitions use a single countably infinite constant set Con, abstracting from model-specific constants and issues such as blank-node semantics and literal entailment.The appendix complements the paper’s example-driven discussion with formal definitions while following previous graph-model conventions.Source: B FORMAL DEFINITIONS · p. 113, §B.1 · p. 113

B.1 Data Graph Models

• Directed edge-labelled graphs comprise nodes, edge labels, and labelled edges, without requiring nodes and labels to be disjoint or to participate in an edge.Graph unions and related set operations are interpreted through their edge sets, with induced nodes and labels.Source: §B.1.1 · p. 113
• Heterogeneous graphs add node labels, while property graphs represent node and edge identifiers, labels, and property–value pairs through explicit mappings.The definitions permit multiple labels and multiple values for a property, treating such variations as syntactic.Source: §B.1.2 · pp. 113–114
• A graph dataset consists of a default directed edge-labelled graph plus optionally named graphs with unique names, and an RDF dataset specializes this model with RDF graphs and blank-node or IRI names.The default graph is unnamed, whereas named graphs can also occur as nodes in the default graph.Source: §B.1.4 · p. 114

B.2 Querying

• Graph querying is formalized with patterns over constants and variables, then extended with relational-style operators and navigational path expressions for directed edge-labelled and property graphs.Path expressions support inverse, Kleene star, concatenation, and disjunction; regular path queries return endpoint pairs under SPARQL 1.1-style semantics.Source: §B.2 · p. 114, §B.2.1 · p. 114, §B.2.3 · p. 116

B.3 Schema

• The schema formalism generalizes semantic schemata, while validating schemata define shapes using logical conditions, references, and bounded or unbounded outgoing-edge constraints.A shapes schema maps shape labels to shapes, and validation is defined through shape evaluations over nodes and a total shapes map.Source: §B.3.1 · p. 117, §B.3.2 · p. 118
• A graph is valid under a shapes schema and target when a shapes map agrees with shape evaluations and every targeted node satisfies its required shape.Targets may be selected manually, by node types, or through graph-query results; the formal example shows that targeting EID16 invalidates the graph because EID16 does not satisfy Event.Source: §B.3.2 · pp. 118–119
• Emergent schemata are formalized with quotient graphs that merge nodes according to a partition while preserving edges between the resulting parts.Potential quotient graphs are exponential in the number of input-node partitions, with practical partitions often induced by shared types, topology, simulation, or bisimulation.Source: §B.3.3 · p. 119

B.3.3 Emergent schema

• Simulation requires each source edge to be matched by a corresponding target edge, while bisimulation adds the reverse condition; bisimulation is an equivalence relation and supports bisimilar quotient graphs.A quotient graph always simulates its input under the set-membership definition, but need not bisimulate it; concise bisimilar quotients can merge nodes while preserving bisimilarity.Source: §B.3.3 · pp. 119–120

B.4.1 Annotation domain

• An annotation domain is an idempotent, commutative semiring whose induced partial order supports well-defined reasoning and querying over annotated graphs.Annotated graph edges carry values from the semiring’s annotation set, with the day-set example instantiating ⊕ as union and ⊗ as intersection.Source: §B.4.1 · p. 120

B.5.1 Graph interpretations

• Graph interpretations map constants into a domain graph, and graph entailment under semantic conditions requires every model of one graph to model the other.Under the Closed World Assumption, positive edges not entailed by the graph and semantic conditions are assumed false; under the Open World Assumption, they are not thereby negated.Source: §B.5.1 · pp. 121–122

B.5.2 Rules

• Rules derive graph extensions by matching body patterns and substituting their mappings into heads, with recursive application reaching a least-model fixpoint.A rule set is correct when its least model contains only entailed data and complete when it contains every entailed edge; the cited RDFS example is correct but incomplete.Source: §B.5.2 · p. 122

B.5.3 Description Logics

• Description Logic knowledge bases comprise A-Box assertions, T-Box class axioms, and R-Box relation axioms, interpreted over individuals, classes, and binary relations.A DL interpretation is a domain paired with a function mapping individuals to domain elements, classes to subsets, and relations to pairs of domain elements.Source: §B.5.3 · p. 123
• DL entailment holds when every model of K1 is also a model of K2, allowing axioms such as flight ⊑connectsTo to entail corresponding relation assertions.Under the Open World Assumption, a model may contain facts not implied by the knowledge base without violating modelhood.Source: §B.5.3 · p. 123
• Unrestricted combinations of Description Logic axioms make entailment undecidable, so practical DLs restrict features to trade expressivity against entailment complexity.The base language ALC supports Boolean class constructors and existential or universal restrictions, while extensions add transitivity, relation inclusions, nominals, inverses, functionality, and number restrictions under limitations.Source: §B.5.3 · pp. 123–124
• OWL 2 DL roughly corresponds to SROIQ, but only a subset of graphs translates into well-formed Description Logic ontologies because some graph axioms are not expressible in DL.For example, the OWL event axiom translates to ∃venue.⊤⊑Event, whereas nested subproperty chains such as “subTaxonOf ⊑⊑” are syntactically invalid.Source: §B.5.3 · p. 124

B.6.1 Graph parallel frameworks.

• Graph parallel frameworks operate on directed vector-labelled graphs whose node and edge feature vectors provide the initial computational state.Node and edge types, attributes, and weights can be encoded in feature vectors, typically with fixed dimensionalities.Source: §B.6.1 · pp. 124–126
• A graph parallel framework uses message, aggregation, and termination functions to iteratively update node vectors from local neighbourhood information, with adaptable message directions and optional global operations.The framework can instantiate PageRank by passing damped, degree-normalized scores, aggregating incoming scores, and stopping after a fixed number of iterations.Source: §B.6.1 · pp. 126–127

B.6.2 Knowledge graph embeddings.

• Knowledge graph embeddings map entities and relation labels to tensors and score triples through a plausibility function, learning to rank positive edges above corrupted negative edges.Models vary in their tensor, vector, or matrix representations and in the operators used to compute plausibility.Source: §B.6.2 · pp. 127–128
• ComplEx, SimplE, and TuckER [30] are fully expressive given sufficient dimensionality, whereas DistMult [568] is not; practical dimensions for full expressivity may be impractical or undesirable.Full expressivity guarantees the ability to correctly partition arbitrary disjoint positive and negative edge sets, but does not ensure feasible model sizes.Source: §B.6.2 · p. 128
• Convolutional graph methods apply learned kernels across graph-related tensor or matrix representations, with multiple kernels producing multiple convolution outputs.The section notes that the operator follows the neural-network convolution convention and abstracts away implementation details such as edge handling and stride.Source: §B.6.2 · pp. 131–132, §B.6.3 · p. 132

B.6.3 Graph neural networks.

• Graph neural networks aggregate node and edge neighbourhood features recursively to a fixpoint or through a fixed stack of layers, with parameters learned from labelled examples.Recursive GNNs use shared aggregation and output functions, whereas non-recursive GNNs may use a different aggregation function at each of l layers; convolutional variants use convolutional operators.Source: §B.6.3 · pp. 132–133
• GNNs and graph-parallel frameworks both propagate neighbourhood information toward convergence, but GPF functions are user-defined while GNN functions are generally learned from labelled examples.GNNs can incorporate outgoing neighbours through inverse edges or modified aggregation, while neighbourhood-only variants have limited expressivity and globally shared vectors can provide greater expressiveness.Source: §B.6.3 · p. 133

B.6.4 Symbolic learning.

• Hypothesis induction seeks graph hypotheses that entail all positive edges without entailing negatives, remain consistent with the background graph, and do not independently entail the positives.The task is defined over a graph entailment relation and a set of candidate hypothesis graphs; an example shows a symmetric type hypothesis satisfying the positive and negative-edge requirements.Source: §B.6.4 · p. 134
• Hypothesis mining instead scores non-entailed hypotheses for explaining a graph while minimizing entailed negative edges, using support or confidence under closed-, open-, or partial-completeness assumptions.The partial completeness assumption is presented as a practical heuristic because knowledge graphs are incomplete, while implementations range from discrete refinement searches to differentiable rule mining.Source: §B.6.4 · pp. 134–135

• A property graph pattern specifies node and edge identifiers, labels, property–value pairs, and a mapping from each edge to its endpoint nodes.It is represented as Q = (V, E, L, P, U, e, l, p), with labels and properties assigned to nodes or edges.Source: A property graph · p. 115
• Graph-pattern evaluation returns mappings that assign every pattern variable to a constant such that the instantiated pattern is a subgraph of the data graph.The evaluation is Q(G) = {μ | μ(Q) ⊆ G and dom(μ) = Var(Q)}.Source: A property graph · p. 115
• Under homomorphism-based semantics, mappings may identify distinct node or edge variables with the same constant, unlike isomorphism-based semantics.The paper henceforth assumes the more general homomorphism-based semantics.Source: A property graph · p. 115
• Complex graph patterns are built recursively from graph patterns using projection, selection with boolean conditions, join, union, difference, and left-join operators.These operators combine or filter pattern evaluations; syntactic operators such as left-join do not add expressivity to the query language.Source: A property graph · pp. 115–116
• Complex-pattern evaluation uses projected mappings, boolean satisfaction, and compatibility requiring shared variables to map to the same constants before mappings are combined.The join evaluation forms unions of compatible mappings from the component pattern evaluations.Source: A property graph · p. 116