Knowledge Graph Navigator (KGN)

A primary challenge in AI is bridging the gap between unstructured human language and structured knowledge. In this chapter, we build a Knowledge Graph Navigator (KGN) in Scala 3. KGN parses unstructured natural language sentences, extracts recognized entities, resolves them to global Uniform Resource Identifiers (URIs) on DBpedia, and queries the DBpedia SPARQL endpoint to fetch detailed biographies and discover relationships between the entities.

All code is in source-code/kgn.

This chapter joins the two preceding ones. The NLP chapter found names in text; the Semantic Web chapter queried structured knowledge graphs. The gap between them is the grounding problem: a knowledge graph knows facts about http://dbpedia.org/resource/Apple_Inc., but a person writes “Apple”. Connecting the words people write to the exact things a machine knows about is the task called entity linking (or named-entity disambiguation).

It helps to separate two steps that sound alike. Named Entity Recognition, from the NLP chapter, finds the span of text that names something (“Steve Jobs”). Entity linking goes further and resolves that span to one specific, unique identifier in a knowledge base. The hard part is ambiguity: “Apple” is a company and a fruit, “Washington” is a person, a city, and a state, and “Jordan” is a country and several people. A mention on its own does not pick out one entity, so a linker must choose.

Two families of solution exist. Learned linkers (such as DBpedia Spotlight or modern neural systems) use the surrounding context and statistics to guess the intended entity. KGN takes the simpler gazetteer route: it keeps dictionaries that map known names directly to URIs and resolves ambiguity by a fixed category priority. This needs no training and is fully transparent, at the cost of missing names absent from its lists and resolving ambiguous names by rule rather than by context. For a bounded domain it is an effective and inspectable design.

KGN implements a lightweight pipeline that mirrors the structure of the grounding problem:

1. Entity Mapping: Parse input text and match n-grams against dictionary lists (gazetteers) linking common terms to DBpedia URIs.
2. Detail Retrieval: For each extracted entity, query its properties (e.g. spouse, Alma Mater, net income, population) using specialized SPARQL templates.
3. Relationship Discovery: Query DBpedia to find semantic edges that directly connect pairs of extracted entities.

This shape, extract then retrieve then reason, is worth noticing because it reappears in modern systems. A retrieval-augmented generation (RAG) pipeline and a tool-using LLM agent both follow the same arc: turn a question into a structured lookup, fetch facts from an external source, then combine them into an answer. KGN is a fully classical version of that pattern, with dictionaries and SPARQL standing in for embeddings and a language model.

In kgn/TextToDbpediaUris.scala, we load maps for categories such as people, companies, cities, and countries from text files. Each gazetteer is a tab-separated file pairing a surface name with its DBpedia URI, and the loader builds one dictionary per category (nine categories, several thousand entries in total).

When text is entered, the engine tokenizes it and performs a sliding-window n-gram match to resolve terms to DBpedia URIs. Crucially, it tries the longest match first, testing a 3-gram before a 2-gram before a single word:

The longest-match rule is what makes “Apple Computer” resolve as the two-word company rather than as the single word “Apple”, and it advances the index past the whole matched span so each mention is consumed once. Disambiguation happens inside tryMatch, which checks the categories in a fixed priority order, person first, then city, company, country, and the rest:

This ordering is the whole disambiguation policy: when a name appears in more than one gazetteer, the first category in checkOrder wins. It is a blunt rule compared to a context-aware linker, but it is predictable, and for the demo queries it resolves each mention correctly. If a match is found, the URI is cached (e.g., "Bill Gates" maps to <http://dbpedia.org/resource/Bill_Gates>).

Once we have a resolved DBpedia URI, we want to retrieve its properties. We define template queries for each entity type in kgn/EntityDetail.scala. These templates lean on two SPARQL features that matter when querying a large, messy, real-world graph:

The first feature is OPTIONAL. Recall the Open World Assumption from the last chapter: a real entity may be missing a birthplace or a spouse, and a plain graph pattern that required every field would return nothing for such an entity. OPTIONAL acts like a left outer join, so a match still succeeds when the optional fields are absent, and only the label is truly required. The second feature is GROUP_CONCAT, an aggregation function that collapses many values into one string. DBpedia often lists several birthplaces or two alma maters for one person, and GROUP_CONCAT folds them into a single |-separated field so each entity comes back as one tidy row. The FILTER (lang(?label2) = 'en') clauses keep only English labels, since DBpedia stores text in dozens of languages. Similar templates are defined for companies (fetching net income and employee counts) and cities (fetching coordinates and population density).

To discover how two entities relate, we search for direct predicates connecting their URIs. This is the same technique as the Bill Gates and Microsoft query from the Semantic Web chapter: fix the subject and object, leave the predicate as a variable, and let the graph report every edge between the two nodes. In kgn/EntityRelationships.scala, we add a filter to remove noise:

The FILTER (!regex(str(?p), 'wikiPage', 'i')) clause drops predicates whose names contain “wikiPage”. DBpedia records a great many wikiPageWikiLink edges that merely mean one Wikipedia article links to another, which says nothing about a real-world relationship. Filtering them out leaves the meaningful predicates like founder and keyPerson. The driver in kgn/Main.scala runs this query over every pair of extracted entities, a Cartesian product that costs queries for entities, which is fine for the handful of names in a sentence.

The application in kgn/Main.scala hosts an interactive loop. Users can enter sentences or run built-in demos.

Launch the shell with:

If we input the query sentence:

Steve Jobs worked at Apple Computer and visited IBM

KGN tokenizes the text, matches the proper names, resolves them to DBpedia URIs, queries their properties, and finds relations:

The first three lines of output are the entity-linking result: each mention is shown with its token span and the URI it resolved to. Note that “Apple Computer” linked to Apple_Inc. as a two-word company, exactly the longest-match behavior at work. The detail queries then returned Jobs’s birthplace, alma mater, and spouse, and Apple’s and IBM’s industry, net income, and headcount, each assembled by GROUP_CONCAT from possibly many underlying triples. Finally, the relationship query discovered that Steve Jobs was a founder, key person, and board member of Apple Inc. KGN answered a question no single Wikipedia sentence states, by grounding the names in a knowledge graph and querying the structure directly.