Knowledge Graphs

Graph-Based Knowledge Representation and Large-Scale Structured Information

Introduction

Knowledge graph: large-scale knowledge base organizing information as network of entities and relations. Entities: concepts, objects, people, places (nodes). Relations: connections between entities (edges). Graph structure mirrors real-world relationships, enabling intuitive representation and powerful reasoning.

Modern knowledge graphs: Google Knowledge Graph, DBpedia, Wikidata, YAGO. Store billions of facts describing world knowledge. Power web search, recommendation systems, semantic reasoning. Combine structured data (database rigor) with flexible graph (natural relationships).

Key advantages: represent complex relationships, scale to billions of facts, enable knowledge inference, integrate data from multiple sources. Enable semantic search: understand meaning beyond keywords. Foundation for knowledge-driven AI systems.

"Knowledge graphs embed world knowledge in interconnected graph structure. Bridging structured databases and natural semantics, enable both precise reasoning and approximate similarity-based inference." -- Semantic web and knowledge systems

Graph Representation Basics

Graph Structure

Graph: set of nodes (vertices) and edges. Directed graph: edges have direction (A→B). Knowledge graphs typically directed: relation has subject and object. Labeled: edge labels indicate relation type.

Node Representation

Nodes represent entities. Each node has unique identifier (URI, ID). May contain attributes: name, description, type. Nodes grouped by category: Person, Place, Organization, etc.

Edge Representation

Edge represents relation between two nodes. Subject-Relation-Object (SRO) triple: (john, knows, mary). Relation type determines semantics. May have properties: time, confidence, source.

Example Graph

Nodes:
- John (Person)
- Google (Company)
- Python (Language)

Edges:
- (John, works-at, Google)
- (John, knows, Python)
- (Google, founded-in, 1998)
- (Google, develops, Python-libraries)

Forms interconnected knowledge about John, Google, skills.

Graph Properties

Degree: number of edges connected to node. In-degree (incoming), out-degree (outgoing). Path: sequence of edges connecting nodes. Cycle: path returning to start. Hub: high-degree node. Clustering: grouping tightly connected nodes.

RDF Triples and Semantic Web

RDF Triple Format

RDF (Resource Description Framework): standardized triple format. Subject-Predicate-Object (SPO). Example: (John, age, 30). Subject: entity. Predicate: relation type. Object: value or entity.

RDF Examples:
(john, knows, mary) -- john knows mary
(john, age, 30) -- john's age is 30
(apple, color, red) -- apple color is red
(john, father, michael) -- john's father is michael

URIs for Global Identification

Each element identified by URI (Uniform Resource Identifier). Enables global interoperability. Multiple sources use same URI for same entity. Example: http://dbpedia.org/resource/John_Smith uniquely identifies person.

Semantic Web Standards

RDF: data model. RDF Schema: vocabulary layer (defines classes, properties). OWL (Web Ontology Language): adds semantics (constraints, inference rules). SPARQL: query language for knowledge graphs.

Data Integration via RDF

Multiple sources convert to RDF. Link entities across sources via URIs. Example: DBpedia (Wikipedia), Wikidata, YAGO all represent same entities using compatible URIs. Seamless integration.

Advantages of Standardization

Interoperability: systems share knowledge without custom integration. Scalability: add new sources without changing system. Extensibility: add new predicates without schema changes. Open standards enable collaboration.

Entities and Relations

Entity Types

Named entities: Person (John, Mary), Place (Paris, Tokyo), Organization (Google, WHO). Concepts: abstract ideas (Freedom, Democracy), categories (Mammal, Disease). Events: actions (Election, Wedding). Resources: publications (Article, Book).

Entity Disambiguation

Multiple entities share names. Name "John" refers to thousands of people. Knowledge graph must disambiguate: John_Smith_born_1980, John_Smith_politician_USA. Use identifiers (IDs) and attributes (birth date, profession) to distinguish.

Relation Types

Taxonomic: is-a (subclass), instance-of (category membership). Semantic: knows, works-for, located-in. Attributes: age, birthplace, height. Domain-specific: medically-treats, teaches-course. Hundreds to thousands of relations in large graphs.

Relation Properties

Symmetric: X married-to Y implies Y married-to X. Antisymmetric: X father-of Y implies Y not father-of X. Transitive: X ancestor-of Y, Y ancestor-of Z implies X ancestor-of Z. Important for inference.

Temporal Relations

Time-aware relations: when relation holds. (John, works-at, Google, 2010-2020). Enables historical knowledge. Temporal reasoning: infer facts at specific times.

Uncertainty and Confidence

Some facts uncertain. Assign confidence scores. (John, age, 30, confidence: 0.9). From extraction systems: confidence reflects extraction quality. Enables reasoning under uncertainty.

Schema and Ontology Layer

Schema Definition

Schema: vocabulary of entity types and relations. Defines what entities/relations permitted. Example: Person type with properties (name, age, birthplace). Relation type knows connects two Persons.

Type Hierarchy

Entity types organized hierarchically. Animal is superclass of Mammal, Bird. Mammal is superclass of Dog, Cat. Inheritance: Dog inherits properties from Mammal and Animal.

Ontology Standards

OWL (Web Ontology Language) expresses ontologies. Defines classes, properties, constraints. Subclass relations, property domains/ranges, cardinality constraints, etc.

Ontology Example:
Person:
 properties: name, age, email
 constraints: age >= 0, age < 150
Knows relation:
 domain: Person
 range: Person
 symmetric: true
Works-for relation:
 domain: Person
 range: Organization

Constraint Enforcement

Schema enforces consistency. Relation knows should only connect Persons. Adding (John, knows, Paris) violates schema. Enables quality control, error detection.

Semantic Inference

Ontology enables inference beyond explicit facts. If Mammal is-a Animal and Dog is-a Mammal, infer Dog is-a Animal. If Person is-a Organism and John is-a Person, infer John is-a Organism. Derive implicit knowledge.

Reasoning in Knowledge Graphs

Rule-Based Inference

Inference rules derive new facts. Example: If (X, father, Y) and (Y, father, Z), then (X, grandfather, Z). Apply rules to graph, generate new triples. Closure: repeatedly apply until no new facts.

Type Inference

Infer entity types from relations. (John, works-at, Google) and (works-at domain: Person) infers John is-a Person. Relation domain/range constraints enable type inference.

Relation Inference

Symmetric relations: (X, knows, Y) implies (Y, knows, X). Transitive: ancestor, descendant relations propagate. Inverse: (X, child, Y) equivalent to (Y, parent, X).

Logical Consistency

Check for contradictions. Disjoint types: Person and Place cannot be same entity. Logical constraints enforced. Detection: (John, age, 30) and (John, age, 50) contradictory. Report inconsistencies.

Approximate Reasoning

Real knowledge graphs incomplete and noisy. May not have rules for all inferences. Approximate methods: similarity-based reasoning, statistical inference. Accept uncertain conclusions.

Query Answering

Answer complex queries: "Who did John's father work for?" Traverse graph: find John's father, find his employers, return results. SPARQL query language enables structured queries.

Graph Embeddings and Vector Representations

Embedding Concept

Represent entities and relations as dense vectors in low-dimensional space. Embedding captures semantic similarity: similar entities close in embedding space. Enable machine learning on graph data.

TransE Model

Simple embedding model: relation translation. Embedding: e_subject + e_relation ≈ e_object. Analogous to word embeddings (king - man + woman ≈ queen). Scalable, interpretable.

Example (simplified):
Vector space: 3-dimensional
John: [0.5, 0.2, 0.1]
Mary: [0.6, 0.1, 0.15]
knows: [0.1, -0.1, 0.05]

Check: John + knows ≈ Mary?
[0.5, 0.2, 0.1] + [0.1, -0.1, 0.05] ≈ [0.6, 0.1, 0.15] ✓
Predicts (John, knows, Mary) likely true.

DistMult Model

Score triple using: s_i * r_i * o_i (element-wise product). Captures symmetric and antisymmetric relations. More expressive than TransE.

Complex Embeddings

Use complex-valued vectors. Enable more expressive representations. Handle various relation types (symmetric, antisymmetric, compositional). State-of-art performance.

Learning Embeddings

Train embeddings to maximize score of true triples, minimize score of false triples. Ranking loss: true triple ranked higher than false. Large-scale optimization.

Applications

Entity similarity: find related entities. Clustering: group similar entities. Classification: predict entity types. Recommendation: suggest items to users based on graph structure.

Query and Retrieval

SPARQL Query Language

Standard query language for RDF graphs. SELECT-WHERE pattern. Example: "Find all people who work for Google."

SPARQL Example:
SELECT ?person
WHERE {
 ?person works-for dbpedia:Google .
 ?person birthPlace ?city .
 ?city inCountry dbpedia:USA .
}

Returns: all US-born people working for Google

Query Processing

Parse query to pattern. Find matching subgraphs in knowledge graph. Return results. Challenges: large graphs, complex queries need efficient algorithms. Join ordering crucial for performance.

Full-Text Search

Search by entity names, descriptions. Combine with graph structure: find entity, then traverse graph. Google Knowledge Graph search: "Bill Gates" returns entity, then facts about Bill Gates.

Semantic Search

Understand query intent, not just keywords. "CEO of Apple" understood as Apple's CEO, not just mentions. Entity linking maps query to graph entities. Relation extraction identifies relations in query.

Question Answering

Answer natural language questions: "Who founded Google?" Parse question, identify query pattern, retrieve answer. Knowledge graphs supply facts. Combines NLP + knowledge graphs.

Traversal and Exploration

Browse graph interactively. Click on entity, see related entities and facts. Breadth-first or relevance-based ranking. Enables knowledge exploration, discovery.

Scalability and Challenges

Scale of Modern Knowledge Graphs

Google Knowledge Graph: billions of entities, hundreds of billions of facts. Wikidata: 50+ million entities, 1+ billion facts. Scale requires distributed systems, specialized storage.

Storage Solutions

Graph databases: specialized for graph data (Neo4j, ArangoDB). RDF stores: optimized for triples (Virtuoso, Jena). Distributed storage: sharding graphs across machines. Vertical partitioning by relation type.

Query Optimization

Large graphs slow queries. Indices on entity/relation types. Caching popular queries. Approximation: answer on sample. Distributed query processing: parallelize across machines.

Data Quality Issues

Extraction from text: noisy, incomplete. Duplicate entities: multiple URIs same entity. Inconsistent data: conflicting facts. Need cleaning, deduplication, fusion.

Knowledge Graph Construction

Information extraction from unstructured text. Named entity recognition identifies entities. Relation extraction identifies relations. Link prediction fills gaps. Combines NLP, ML, symbolic reasoning.

Temporal Evolution

Knowledge graphs evolve: entities added, removed, updated. Handle versions, temporal ranges (fact valid 2010-2020). Temporal reasoning, time-aware queries.

Integration Across Sources

Multiple knowledge graphs independently created. Merge: entity alignment, relation matching. Reconcile conflicts: choose trustworthy sources. Enable integrated reasoning.

Applications in AI Systems

Web Search and Information Retrieval

Google Search uses Knowledge Graph to enhance results. Searching "Paris" shows facts (population, monuments, history). Knowledge cards provide rich information beyond traditional links.

Recommendation Systems

Knowledge graphs model user-item-attribute relationships. Collaborative filtering: similar users like similar items. Content-based: recommend items similar to user's history. Graph structure guides recommendations.

Question Answering Systems

Convert question to graph query. "When was Eiffel Tower built?" Find Eiffel Tower entity, retrieve construction-date property. Complex questions: multi-hop reasoning across graph.

Entity Linking and Disambiguation

Link text mentions to graph entities. "John works at Apple" disambiguates John (among thousands), Apple (the company). Enable automated annotation, knowledge extraction.

Knowledge Discovery

Analyze graph structure find patterns, anomalies. Clustering: similar entities. Frequent patterns: common subgraphs. Anomaly detection: unusual connections. Scientific discovery from biomedical knowledge graphs.

Semantic Reasoning

Enable semantic web: machines understand meaning. Interlinked ontologies enable cross-domain reasoning. Medical + biological + chemical knowledge graphs combined for drug discovery.

Business Intelligence

Enterprise knowledge graphs model company data: employees, products, sales, relationships. Enable complex queries, insights. Identify key employees, sales patterns, supply chain relationships.

References

  • Hogan, A., et al. "Knowledge Graphs." arXiv preprint arXiv:2003.02320, 2020.
  • Nickel, M., Murphy, K., Tresp, V., and Kriegel, H. P. "A Review of Relational Machine Learning for Knowledge Graphs." Proceedings of the IEEE 104.1, 2015.
  • Paulheim, H. "Knowledge Graph Refinement: A Survey of Approaches and Evaluation Methods." Semantic Web 8.3, 2017.
  • Suchanek, F. M., Kasneci, G., and Weikum, G. "YAGO: A Large Ontology from Wikipedia and WordNet." Web Semantics: Science, Services and Agents on the World Wide Web 6.3, 2008.
  • W3C. "RDF 1.1 Concepts and Abstract Syntax." https://www.w3.org/TR/rdf11-concepts/, 2014.