Knowledge Graph Navigator
The Knowledge Graph Navigator (which I will often refer to as KGN) is a tool for processing a set of entity names and automatically exploring the public Knowledge Graph DBPedia using SPARQL queries. I wrote KGN in Common Lisp for my own use to automate some things I used to do manually when exploring Knowledge Graphs, and later thought that KGN might be useful also for educational purposes. KGN uses NLP code developed in earlier chapters and we will reuse that code with a short review of using the APIs.
Please note that the example is a simplified version that I first wrote in Common Lisp and is also an example in my book Loving Common Lisp, or the Savvy Programmer’s Secret Weapon that you can read free online.
The code for this application is in the directory kgn and this example is pre-configured to use uv.
The spaCy English language model that we used in the earlier chapter on natural language processing is declared as a dependency in kgn/pyproject.toml, so uv sync (or the first uv run) installs everything.
The following listing shows the text based user interface for this example. This example application asks the user for a list of entity names and uses SPARQL queries to discover potential matches in DBPedia.
1 $ uv run hy kgn.hy
2 Enter a list of entities: Bill Gates worked at Microsoft
3 Generated SPARQL to get DBPedia entity URIs from a name:
4 select distinct ?s ?desc { ?s ?p "Bill Gates"@en . ?s <http://dbpedia.org/ontology/description> ?desc . FILTER (lang(?desc) = 'en') . ?s <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://dbpedia.org/ontology/Person> . } limit 15
5 Generated SPARQL to get DBPedia entity URIs from a name:
6 select distinct ?s ?desc { ?s ?p "Microsoft"@en . ?s <http://dbpedia.org/ontology/description> ?desc . FILTER (lang(?desc) = 'en') . ?s <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://dbpedia.org/ontology/Organisation> . } limit 15
7 Please select entities from the list below:
8 1. Bill Gates || English footballer (1944–2023)...
9 2. Bill Gates || American businessman, investor, and philanthropist (born 1955)...
10 3. Bill Gates || American politician...
11 4. Bill Gates || American politician and a Republican member of the Arizona House of Re...
12 5. Microsoft || American multinational technology corporation...
13 6. Microsoft || subsidiary of Microsoft, which is developing Skype...
14 7. Microsoft || organization...
15 8. Microsoft || now-defunct American electronic sports league...
16 9. Microsoft || game development studio...
17 10. Microsoft || working group...
18
19 Enter the numbers of the entities you want to process, separated by commas (e.g., 1, 3): 2, 5
20 Generated SPARQL to get relationships between two entities:
21 SELECT DISTINCT ?p { <http://dbpedia.org/resource/Bill_Gates> ?p <http://dbpedia.org/resource/Microsoft> . FILTER (!regex(str(?p), 'wikiPage', 'i')) } LIMIT 5
22 Generated SPARQL to get relationships between two entities:
23 SELECT DISTINCT ?p { <http://dbpedia.org/resource/Microsoft> ?p <http://dbpedia.org/resource/Bill_Gates> . FILTER (!regex(str(?p), 'wikiPage', 'i')) } LIMIT 5
24
25 Discovered relationship links:
26 [['<http://dbpedia.org/resource/Microsoft>',
27 '<http://dbpedia.org/resource/Bill_Gates>',
28 'http://dbpedia.org/ontology/foundedBy'],
29 ['<http://dbpedia.org/resource/Microsoft>',
30 '<http://dbpedia.org/resource/Bill_Gates>',
31 'http://dbpedia.org/property/founders']]
32 Enter a list of entities: quit
Many DBPedia entities have the label “Bill Gates” or “Microsoft”, so the user selects the ones they mean by typing their index numbers. In the last example we chose indices 2 and 5:
1 Enter the numbers of the entities you want to process, separated
2 by commas (e.g., 1, 3): 2, 5
Each discovered relationship link is a list of a subject, an object, and the property that links them; here DBPedia tells us that Microsoft was founded by Bill Gates.
Note: in the last listing, if you run this example yourself you will see that generated SPARQL queries are colorized for better readability. This colorization does not appear in the last listing.
After listing the generated SPARQL for finding information for the entities in the query, KGN searches for relationships between these entities. These discovered relationships can be seen at the end of the last screen shot. Please note that this step makes O(n^2) SPARQL queries where n is the number of entities. Local caching of SPARQL queries to DBPedia helps make processing many entities possible.
Review of NLP Utilities Used in Application
We covered NLP in a previous chapter, so the following is just a quick review. The NLP code we use is near the top of the file kgn.hy:
1 ;; Knowledge Graph Navigator (KGN): find entities in the user's text, look
2 ;; them up on DBpedia, and discover relationships between the selected ones.
3
4 (import pprint [pprint])
5 (import spacy)
6
7 (import textui [select-entities get-query])
8 (import kgnutils [dbpedia-get-entities-by-name])
9 (import relationships [entity-results->relationship-links])
10
11 (setv nlp-model (spacy.load "en_core_web_sm"))
12
13 (defn entities-in-text [s]
14 "Return a dictionary mapping spaCy entity types to the entity names in S."
15 (setv ret {})
16 (for [entity (. (nlp-model s) ents)]
17 (.append (.setdefault ret entity.label_ []) entity.text))
18 ret)
The function entities-in-text uses the setdefault dictionary method on line 17: it returns the list stored for an entity type, first storing a new empty list if this is the first entity of that type. Here is an example use of this function:
1 => (kgn.entities-in-text "Bill Gates, Microsoft, Seattle")
2 {'PERSON': ['Bill Gates'], 'ORG': ['Microsoft'], 'GPE': ['Seattle']}
The entity type “GPE” indicates that the entity is some type of location.
SPARQL Utilities
We use the standard Python library requests to access the DBPedia servers. The following code is found in the file sparql.hy and also provides support for using WikiData. We only use DBPedia in this chapter but when you start incorporating SPARQL queries into applications that you write, you will also probably want to use WikiData.
The function do-query-helper contains generic code for SPARQL queries and is used in functions wikidata-sparql and dbpedia-sparql:
1 ;; Helper functions to run SPARQL queries against the Wikidata and DBpedia
2 ;; public endpoints.
3
4 (import requests)
5
6 (setv wikidata-endpoint "https://query.wikidata.org/sparql")
7 (setv dbpedia-endpoint "https://dbpedia.org/sparql")
8
9 ;; Public SPARQL endpoints ask clients to identify themselves.
10 (setv headers {"User-Agent" "HyLangBook-KGN/1.0 (https://github.com/mark-watson/hy-lisp-python-book)"
11 "Accept" "application/sparql-results+json"})
12
13 (defn do-query-helper [endpoint query]
14 "Run QUERY on ENDPOINT and return one list per result row, containing a
15 [variable value] pair for each variable bound in that row."
16 (setv response (requests.get endpoint
17 :params {"query" query "format" "json"}
18 :headers headers
19 :timeout 30))
20 (.raise-for-status response)
21 (setv json-data (.json response))
22 (setv vars (get json-data "head" "vars"))
23 (lfor binding (.get (get json-data "results") "bindings" [])
24 (lfor var vars
25 :if (in var binding) ; OPTIONAL variables may be unbound
26 [var (get binding var "value")])))
27
28 (defn wikidata-sparql [query]
29 (do-query-helper wikidata-endpoint query))
30
31 (defn dbpedia-sparql [query]
32 (do-query-helper dbpedia-endpoint query))
Public SPARQL endpoints are shared resources, so we send a User-Agent header that identifies our program (the WikiData endpoint rejects requests without one) and use a timeout so that a slow server cannot hang the application. The call to raise-for-status turns an HTTP error, such as a malformed query, into a Python exception instead of a confusing error when we try to parse the response as JSON. The :if clause in the inner lfor on line 25 skips variables that are not bound in a result row, which can happen with SPARQL OPTIONAL patterns.
Here is an example query (manually formatted for page width):
1 $ uv run hy
2 => (import sparql)
3 => (sparql.dbpedia-sparql
4 "select ?s ?p ?o { ?s ?p ?o } limit 1")
5 [[['s', 'http://www.openlinksw.com/schemas/virtrdf#DefaultQuadMap'],
6 ['p', 'http://www.w3.org/1999/02/22-rdf-syntax-ns#type'],
7 ['o', 'http://www.openlinksw.com/schemas/virtrdf#QuadMap']]]
8 =>
This is a wild-card SPARQL query that will match any of the billions of RDF triples in DBPedia and return just one result.
Utilities to Colorize SPARQL and Generated Output
When I first had the basic functionality of KGN working, I was disappointed by how the application looked as normal text. Every editor and IDE I use colorizes text in an appropriate way so I used standard ANSI terminal escape sequences to implement color highlighting of SPARQL queries.
The code in the following listing is in the file colorize.hy.
1 (import io [StringIO])
2
3 ;; Utilities to add ANSI terminal escape sequences to colorize text.
4 ;; note: the following 5 functions return string values that then need to
5 ;; be printed.
6
7 (defn blue [s] (.format "{}{}{}" "\033[94m" s "\033[0m"))
8 (defn red [s] (.format "{}{}{}" "\033[91m" s "\033[0m"))
9 (defn green [s] (.format "{}{}{}" "\033[92m" s "\033[0m"))
10 (defn pink [s] (.format "{}{}{}" "\033[95m" s "\033[0m"))
11 (defn bold [s] (.format "{}{}{}" "\033[1m" s "\033[0m"))
12
13 (defn tokenize-keep-uris [s]
14 ;; Splits a string into tokens based on whitespace.
15 (.split s))
16
17 (defn colorize-sparql [s]
18 ;; Applies ANSI color codes to a SPARQL query string for terminal formatting.
19 (setv tokens
20 (tokenize-keep-uris
21 (.replace (.replace s "{" " { ") "}" " } ")))
22 (setv ret (StringIO)) ;; ret is an output stream for a string buffer
23 (for [token tokens]
24 (when (> (len token) 0)
25 (if (= (get token 0) "?")
26 (.write ret (red token))
27 (if (in
28 token
29 ["where" "select" "distinct" "option" "filter"
30 "FILTER" "OPTION" "DISTINCT" "SELECT" "WHERE"])
31 (.write ret (blue token))
32 (if (= (get token 0) "<")
33 (.write ret (bold token))
34 (.write ret token)))))
35 (when (not (= token "?"))
36 (.write ret " ")))
37 (.seek ret 0)
38 (.read ret))
39
40 ;;(print (colorize-sparql "select ?s ?p where {?s ?p <http://dbpedia.org/schema/Person>}."))
Text Utilities for Queries and Results
The application low level utility functions are in the file kgnutils.hy. The function dbpedia-get-entities-by-name requires two arguments:
- The name of an entity to search for.
- A URI representing the entity type that we are looking for.
We embed a SPARQL query that has placeholders for the entity name and type. The query matches any resource ?s that has some property with the entity name as its English string value, has the requested type, and has a short description ?desc. The filter expression specifies that we only want English language descriptions by using (lang(?desc) = ‘en’):
1 ;; Utility functions for DBpedia entity retrieval.
2
3 (import sparql [dbpedia-sparql])
4 (import colorize [colorize-sparql])
5
6 (defn sparql-string [s]
7 "Quote S as a SPARQL string literal, escaping backslashes and quotes."
8 (+ "\"" (.replace (.replace s "\\" "\\\\") "\"" "\\\"") "\""))
9
10 (defn dbpedia-get-entities-by-name [name dbpedia-type]
11 "Find DBpedia entities of type DBPEDIA-TYPE that have NAME as an English
12 label. Returns rows of [[\"s\" uri] [\"desc\" short-description]]."
13 (setv query
14 (.format "select distinct ?s ?desc {{ ?s ?p {}@en . ?s <http://dbpedia.org/ontology/description> ?desc . FILTER (lang(?desc) = 'en') . ?s <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> {} . }} limit 15"
15 (sparql-string name) dbpedia-type))
16 (print "Generated SPARQL to get DBPedia entity URIs from a name:")
17 (print (colorize-sparql query))
18 (dbpedia-sparql query))
The function sparql-string (lines 6-8) makes the entity name safe to insert into a query: without escaping, a name containing a double quote character (for example a nickname in quotes) would end the SPARQL string early and break the query. The doubled curly braces {{ and }} in the format string on line 14 produce single braces in the generated query, because single braces mark the places where .format inserts values.
Finishing the Main Function for KGN
We already looked at the NLP code near the beginning of the file kgn.hy. Let’s look at the remainder of the implementation.
We need a dictionary (or hash table) to convert spaCy entity type names to DBPedia type URIs:
1 (setv entity-type-to-type-uri
2 {"PERSON" "<http://dbpedia.org/ontology/Person>"
3 "GPE" "<http://dbpedia.org/ontology/Place>"
4 "ORG" "<http://dbpedia.org/ontology/Organisation>"
5 })
When we get entity results from DBPedia, the descriptions of entities can be long. We want to shorten them so they fit in a single line of the entity selection list that we have seen earlier. The following code defines a description shortening function and also a global variable short-comment-to-uri that maps a shortened description back to the DBPedia URI of the entity it describes:
1 (setv short-comment-to-uri {})
2
3 (defn shorten-comment [comment uri]
4 "Shorten COMMENT to fit on one line and remember which URI it describes."
5 (setv sc (+ (cut comment 0 70) "..."))
6 (setv (get short-comment-to-uri sc) uri)
7 sc)
Finally, let’s look at the main application loop. In line 6 we are using the function get-query (defined in file textui.hy) to get a list of entity names from the user. In line 12 we use the function entities-in-text that we saw earlier to map text to entity types and names; the :if clause on line 13 skips entity types like DATE or MONEY that have no DBPedia type in our table. In the nested loop in lines 14-18 we look up each name on DBPedia, and the destructuring pattern [[_ uri] [_ description]] on line 15 pulls the URI and description out of each result row. Each match is added to the list for its entity type as a string of the form name || short description.
In lines 21-24 we convert the strings for the entities that the user selected back to DBPedia entity URIs. Finally in line 25 we use the function entity-results->relationship-links to find relationships between the user selected entities.
1 (defn kgn []
2 "Main loop: get the user's text, find entities, search DBpedia, and
3 discover relationships between the entities the user selects."
4 (global short-comment-to-uri)
5 (while True
6 (setv query (get-query))
7 (when (in (.strip query) ["quit" "q" ""])
8 (break))
9 (setv short-comment-to-uri {})
10 ;; entities found on DBpedia, as "name || short description" strings
11 (setv found (dfor key entity-type-to-type-uri key []))
12 (for [[key names] (.items (entities-in-text query))
13 :if (in key entity-type-to-type-uri)] ; skip DATE, MONEY, etc.
14 (for [name names
15 [[_ uri] [_ description]] (dbpedia-get-entities-by-name
16 name (get entity-type-to-type-uri key))]
17 (.append (get found key)
18 (+ name " || " (shorten-comment description uri)))))
19 (setv user-selected-entities
20 (select-entities (get found "PERSON") (get found "GPE") (get found "ORG")))
21 (setv uri-list
22 (lfor entity user-selected-entities
23 (get short-comment-to-uri
24 (cut entity (+ 4 (.index entity " || ")) None))))
25 (setv relation-data (entity-results->relationship-links uri-list))
26 (print "\nDiscovered relationship links:")
27 (pprint relation-data)))
The function entity-results->relationship-links is in the file relationships.hy. A single lfor with two loop variables visits every ordered pair of different entities, and for each pair asks DBPedia which properties link the first entity to the second:
1 ;; Discovers relationships between entities using DBpedia queries.
2
3 (import sparql [dbpedia-sparql])
4 (import colorize [colorize-sparql])
5
6 (defn dbpedia-get-relationships [s-uri o-uri]
7 "Return the URIs of properties that directly link S-URI to O-URI in DBpedia."
8 (setv query
9 (.format
10 "SELECT DISTINCT ?p {{ {} ?p {} . FILTER (!regex(str(?p), 'wikiPage', 'i')) }} LIMIT 5"
11 s-uri o-uri))
12 (print "Generated SPARQL to get relationships between two entities:")
13 (print (colorize-sparql query))
14 ;; each result row is [["p" property-uri]]
15 (lfor row (dbpedia-sparql query) (get row 0 1)))
16
17 (defn entity-results->relationship-links [uris]
18 "Return [subject object property] for every DBpedia property that links
19 one of the entity URIS to another."
20 (setv uris (lfor uri uris (+ "<" uri ">")))
21 (lfor e1 uris
22 e2 uris
23 :if (!= e1 e2)
24 p (dbpedia-get-relationships e1 e2)
25 [e1 e2 p]))
Each result row returned by dbpedia-sparql looks like [[“p” property-uri]], so on line 15 (get row 0 1) extracts just the property URI.
If you have not already done so, I hope you experiment running this example application. Expect some delay while DBPedia is accessed, especially when your query contains many entity names; adding a cache is one of the practice problems below.
Wrap-up
If you enjoyed running and experimenting with this example and want to modify it for your own projects then I hope that I provided a sufficient road map for you to do so.
I got the idea for the KGN application because I was spending quite a bit of time manually setting up SPARQL queries for DBPedia and other public sources like WikiData, and I wanted to experiment with partially automating this exploration process.
Optional Practice Problems
To deepen your understanding of KGN, SPARQL, and entity extraction in Hy, try completing the following exercises:
- Extend Entity Types: Currently,
kgn.hyonly extracts and mapsPERSON,GPE(Place), andORG(Organisation) entities to DBpedia types. Modify theentity-type-to-type-uridictionary and the interactive loop to support additional spaCy entity types, such asWORK_OF_ART(mapped to<http://dbpedia.org/ontology/Work>) orEVENT(mapped to<http://dbpedia.org/ontology/Event>). Test your changes with queries containing book/movie titles or historical events. - Implement a Query Caching Layer: Since DBpedia queries over the network can be slow or fail, implement a simple caching layer in
sparql.hy. You can serialize query results to a local JSON file or a SQLite database keyed by the SPARQL query string. If a query is found in the cache, return it immediately; otherwise, fetch it over the network and cache it. - Integrate Wikidata: The
sparql.hyfile defineswikidata-sparqlbut it is not currently used by the application. Modifykgn.hyto allow querying Wikidata as a fallback or side-by-side comparison when looking up entity details. Note that Wikidata’s property URIs and structures are different from DBpedia’s, so you will need to formulate a compatible SPARQL query structure.