We present WoolNet: an online system for exploring paths in a knowledge graph. Specifically, given two or more entities requested by a user, the system finds and visualises paths that connect these entities, forming a topical subgraph. Upon requesting entities, a multi-source path search algorithm is run against an in-memory index of the knowledge graph, with paths displayed as they are found. Running the algorithm for longer (up to a maximum of two minutes) results in the system finding and displaying more paths. Features are provided to filter paths by length and node degree. The system we present and evaluate currently illustrates the use of WoolNet for exploring paths in the Wikidata knowledge graph.
Techniques for graph-based data management have enjoyed renewed interest in recent years, particularly in the context of knowledge graphs [1]. In this setting, graphs provide a flexible model useful for integrating diverse data at large scale, where nodes represent entities, and edges represent relationships between these entities. This idea has given rise to both enterprise knowledge graphs (published by AirBnB, eBay, Facebook, Google, etc.) [1], as well as open knowledge graphs such as Wikidata [2].
A key feature of graph-based data models is the ability to find both direct and indirect connections between entities via paths in the graph. Graph query languages such as Cypher [3], G-CORE [4], GQL [5], Gremlin [6] and SPARQL [7] – and thus the engines supporting them (e.g., [8, 9, 10, 11], among many others) – incorporate a range of features for querying graphs, including finding shortest paths, or finding paths matching regular expressions (via regular path queries and variations thereof) [12]. However, many potential users of knowledge graphs may not be expert in the use of such languages and systems.
We are thus interested in enabling non-expert users to understand what connects two or more entities of interest in that knowledge graph for use-cases involving exploratory search [13] (e.g., for identifying new potential collaborations, potential conflicts of interest or collusion, relations between diseases and drugs, etc.). In this setting, a connection is formed between a pair of entities via a path in the graph. Paths between the same pair of entities may share nodes, as may paths between diferent pairs of entities. Thus a topical subgraph can be formed consisting of the paths between one or more pairs of entities of interest to the user.
To support such users, we propose WoolNet: an online system for finding and visualising paths in knowledge graphs. Having indexed a knowledge graph ofline, the system enables users to search for two or more entities of interest. Upon hitting search, the back-end of the system begins to find paths in the knowledge graph between each pair of entities. As paths are found, they are sent to the front-end and displayed graphically to the user. A public demo of our system is available online at https://woolnet.dcc.uchile.cl.
In the design and development of WoolNet, we address two technical challenges: performance and usability. In order to support finding and visualising paths in real-time over large-scale knowledge graphs, performance is key, for which we propose in-memory indexes and a (to the best of our knowledge, novel) multi-source path finding algorithm. In terms of usability, WoolNet keeps the base user interaction simple, but further provides more advanced features for filtering paths that are not of interest. We then evaluate the performance and usability of WoolNet in the context of the Wikidata knowledge graph.
Popular graph query languages [7, 6, 3, 5] and graph databases [8, 9, 10, 11] provide a range of features for querying paths. Such features require the user to specify their request as part of a structured query, which may be beyond the expertise of many users.
WoolNet rather targets a broader user base, featuring a more accessible user interaction inspired by two systems with similar functionality: RelFinder [14] and WiSP [15]. The system further permits finding paths between three or more nodes, which is not typically supported by graph databases and query languages.
The closest system to WoolNet is RelFinder [14], which permits finding and visualising paths between entities in DBpedia. However, the back-end of RelFinder relies on evaluating SPARQL basic graph patterns of fixed and increasing size to find paths of 1, 2, 3, etc.; note that property paths are not applicable here as they do not support returning the paths themselves, only the nodes connected by paths. This approach is further complicated by the need to query paths in both directions; for paths of length , this would require 2 unions of basic graph patterns with triple patterns each, or joins of unions of 2 triple patterns. Initial experiments delegating such queries to the public Wikidata Query Service [16] often generated timeouts after one minute for paths of length 2, and would not support finding and visualising paths interactively as they were found. We thus ruled out this approach.
Another related system is WiSP (Weighted Shortest Paths) [15], which supports finding paths between Wikidata entities. However, WiSP only finds a single path between a single pair of entities, with a focus on trying to find the most “interesting” path between two entities. Interesting paths are identified based on a combination of path length and graph metrics, where, for example, shorter paths passing through lower-degree nodes are considered more notable.
We define a knowledge graph to be a set of triples, where each triple (, , ) denotes a directed labelled edge of the form →− . We denote by () the set of nodes (or vertices) of ; i.e., () = { | ∃, : (, , ) ∈ or (, , ) ∈ }. We denote by () the set of edge labels (or predicates) of ; i.e., () = { | ∃, : (, , ) ∈ }. Given a node ∈ (), we denote by (, ) the incident edges of in , i.e., {(, , ) ∈ | = or = }. We denote by (, ) the neighbours of in , i.e., (, ) = ((, )) ∖ {}.
We define a 1-length path between ∈ () and ∈ () in as a sequence ⟨(, , )⟩ such that (, , ) ∈ , and {, } = {, }. We define a -length path between and in as a sequence of distinct triples ⟨(1, 1, 1), . . . , (, , )⟩ such that: • ∈ {1, 1} and ∈ {, }, and • for all 1 ≤ ≤ it holds that (, , ) ∈ , and • for all 1 < ≤ , it holds that {− 1, − 1} ∩ {, } ̸= ∅.
Given a knowledge graph , and a set of nodes {1, . . . , } ( ≥ 2) representing entities of interest selected by a user, the goal of WoolNet is to interactively identify and visualise paths in between pairs of nodes and , with 1 ≤ < ≤ . Rather than visualise individual paths, WoolNet visualises the graph – considered a topical subgraph of the knowledge graph – consisting of the union of all edges of relevant paths.
We now provide a technical overview of WoolNet. We start by describing the indexing technique used for the knowledge graphs. We then describe our multi-source graph search algorithm used to find paths between multiple entities. We present the design of the front-end and the user interaction it provides. We end by describing some features we added to filter the paths found and displayed to generate a more concise topical subgraph.
Graph indexing Our aim is to find and visualise paths connecting entities in large knowledge graphs. Our demo – described later – over Wikidata involves a graph of 100 million nodes and 716 million edges. Given the need to navigate significant parts of the knowledge graph in order to find paths, and the fact that such navigation needs to be conducted at runtime while the user waits for such paths to be reported, eficient methods to access and perform lookups on the graph are essential. In particular, given a node ∈ (), the key operation we need to implement eficiently is that of finding all incident edges (, ).
To implement this operation as eficiently as possible, which in turn will increase the rate
at which paths are found and returned to users, we developed and evaluated a number of
static in-memory index structures. In the interest of space, we will present the most eficient
– both in terms of time and space – currently used in the online system. We assume that the
nodes and edge labels of the knowledge graph use an alphabet of integers from the set
{1, . . . , | () ∪ ()|}, applying dictionary encoding if necessary. We then build an adjacency
list Adj consisting of an in-memory multi-dimensional integer array of size | ()| structured
as a trie. Consider for example the graph = {(
Adj =
[[− 4, 3], [− 2, 1], [6, 1]]]
This representation is a three-dimensional array where the initial index corresponds to the
node label; this array has length equal to the maximum node label in the graph. Each index
of this three-dimensional array resolves to a two-dimensional array, with an array for each
unique edge label incident for that particular node (with edges in both directions): the first
element of each such array indicates the edge label, while proceedings elements indicate the
nodes linked by that label. Here, for example, the third element of Adj indicates that node
3 has two incident edges: an incoming edge labelled 2 (we negate edge labels to indicate the
inverse direction) pointing to node 1, and an outgoing edge labelled 4 pointing to node 5. Given
a node , we can then retrieve the incident edges of (i.e., (, )) in time (
This representation is used because (
Path finding Given a knowledge graph , and a set of nodes {1, . . . , } ⊆ (), with ≥ 2, our goal is to find paths between all pairs of nodes and , with 1 ≤ < ≤ .
Rather than finding paths between each pair of nodes, requiring (2) independent searches that do not leverage information found previously (which would be necessary if we used existing graph database technology as our back-end), we propose the multi-source path finding (MSPF) algorithm sketched in Algorithm 1. Given the user-selected nodes {1, . . . , }, and a MAX_LENGTH parameter, we maintain a queue to which we initially add the user-selected nodes. We will conduct a BFS from each such node, expanding the neighbours of each node in turn, and then the neighbours of neighhours, etc. From each initial node, we expand ⌈ MAX_L2ENGTH ⌉ hops. When a node is found in the intersection of two or more BFSs, it witnesses a path between the initial nodes of those BFSs. We further maintain meta-data for each node indicating the BFS in which it was first found, its distance from the initial (user-selected) node in that BFS, and its minimum distance from the initial node in any other BFS. If we find two neighbours with distances in two distinct BFSs summing to less than MAX_LENGTH, we report a path. In practice, we must further store meta-data about the nodes from which we reached the current node, and via which triples, in order to backtrack and report novel edges in the paths; it is also possible for multiple paths to be reported when multiple triples constitute a path of the same length. Crucially, paths are reported immediately as they are found. In terms of optimisation, on line 10 of the algorithm, we construct the neighbours using the Adj index discussed previously.
An example of the algorithm is shown in Figure 2. The algorithm is configured with a MAX_LENGTH parameter, which in this case we assume to be 3. We start from the initial userselected nodes (Q16 in red, and Q24 in blue, in Figure 2a), and expand from one of these nodes to visit its neighbours (in Figure 2b, the red node Q16 is expanded). The algorithm continues, this time expanding the neighbours of the next node (the blue node Q24 per Figure 2c). As we expand nodes, we look for intersections at the frontier of the search, and check the meta-data (a) Initial user-selected nodes (b) Expanding the red node’s neighbours (c) Expanding the blue node’s neighbours (d) A node intersecting both BFSs indicates a path (e) Expanding the red nodes’ neighbours again (f) Another path is found (g) Expanding the blue nodes’ neighbours again (h) Termination and the reported subgraph on intersecting nodes to ensure that they satisfy the maximum length constraint, in which case we backtrack to materialise and report the path (see intersecting node Q12 witnessing a path in Figure 2d). The search continues until we have expanded ⌈ MAX_L2ENGTH ⌉ hops from all of the initial nodes (per Figure 2e, where we expand the red node’s neighbours, finding a new path as seen in Figure 2f, and then expanding the blue node’s neighbours in Figure 2g, terminating with the subgraph shown in Figure 2h; we highlight that in Figure 2g, the node Q4 intersects both BFSs, but its paths are rejected as they exceed the maximum length constraint). The algorithm generalises straightforwardly to the case of having three or more initial nodes.
It is important to note that our MSPF algorithm intends to return the subgraph induced by the corresponding paths found between the nodes, i.e., the union of the sets of triples forming all such paths. We conjecture that the algorithm is sound in the sense that no triple is returned that does participate in such a path, and complete in the sense that all such triples are (eventually) returned by the algorithm. However, Algorithm 1 would require modification to ensure that all relevant paths are reported (rather than the union of the triples that form those paths). User interface In Figure 3 we provide a screenshot illustrating the three principal components of the user interface taken from the demo over Wikidata described in more detail later.1 For clarity, we present an example showing paths between two entities: Alan Turing and Edsger W. Dijkstra. On the left pane, users can search for an entity of interest using an auto-completion dialogue. For example, upon typing “dijkstra”, the user is displayed a list of possible entities that includes Edsger W. Dijkstra. The user can select from the options shown to add an entity to the system. Once the user has selected two or more entities, the user can hit search, and in the main pane, the entities of interest will be displayed. In the back-end, the path-finding algorithm is invoked, and will begin to report paths. As these paths are received, they will be added to the graph displayed. Each node is represented visually with a label and an image (if available). Edges are displayed with direction and with their edge label. Intermediate nodes can be clicked in order to highlight the paths through them; they can also be clicked and dragged to move them. Their default position on the canvas is selected by force-directed layout. From the graph visualised in Figure 3, a user can learn that Turing and Dijkstra were both human, computer scientists and male; that they both spoke English (being the native language of Turing); that Dijkstra won the Turing Award named after Turing; and that Dijkstra was educated at the University of Cambridge, at which Turing worked.
Filtering paths Some queries may generate a graph with many edges making it dificult to view particular connections of interest. Hence we set some constraints on paths, and provide user-controlled filters to narrow down the subgraph.
In terms of constraints, we set MAX_LENGTH to 3 based on initial experience, where 3 is suficient to find some connection between the vast majority of pairs of nodes, whereas paths of length 4 tend to generate irrelevant connections. We also set an overall timeout of 2 minutes for ifnding paths. We further opted to not expand neighbours of high-degree nodes. For example, in Figure 3, numerous nodes can be inserted either between Dijkstra and English or Turing and English while satisfying the maximum length constraint, including papers written by both in English, other people they are connected to that speak English, etc. Thus if a path intersects on a high-degree node, we still include such a path (as shown in Figure 3), but we will not expand that node’s neighbours. As seen later, this heuristic further reduces memory overhead, while also increasing the paths reported per unit of time. We note that these three decisions are largely motivated by our practical goal to reduce the average cost (particularly in memory) of a request, and thus to be able to host a stable service on the Web via commodity hardware.
In terms of filters, at the bottom of the main pane we provide two sliders for filtering paths/edges from the visualisation. The first slider filters paths according to their maximum length. The second filters paths that pass through an intermediate node whose degree is above 10, where 1 ≤ ≤ 8. The idea behind this latter filter is that paths passing through highdegree nodes (such as English or human in Figure 3) are less likely to be of interest to the user [15]. An example of the usage of filters is provided in Figure 4 for a search between Alan Turing, Jensen Huang and Edsger W. Dijkstra: Figure 4a shows the search for paths between the initial entities without using any filter, Figure 4b uses a filter to only show paths with length 2 of less, Figure 4c filters nodes with a degree of more than 105, and Figure 4d uses both filters.
(a) Graph without the use of filters (b) Graph filtering paths longer than 2 edges (c) Graph filtering high-degree nodes (d) Graph applying both filters
We provide an overview of the evaluation of the system in terms of performance (both space and time) and usability.
5 entities 4 entities 3 entities 2 entities 101 102
103 104 Path edges found 105 106 Setup Experiments were run on a machine with 59.6 GB of RAM, a 12-core Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz running Devuan. The index and graph search were implemented in Java (v. 11.0.18). We index a truthy version of Wikidata, considering only triples with Q-code nodes and truthy P-code edge labels. This graph contains 715,906,922 edges and 99,609,308 nodes. Based on preliminary experiments, we do not dictionary encode the graph, but rather use the numeric codes of Wikidata directly as IDs. Processing the dump in order to filter unused triples and load the Adj index required 4.8 hours, occupying 26.9 GB in memory. Performance To test the path finding rate, we selected 10,000 nodes from Wikidata, randomly sampled with weights proportional to the degree of the node. We weighted the random sample as users are more likely to enter high-degree nodes, where the vast majority of nodes in Wikidata have a low degree and are relatively obscure. We then selected 100 sets of 2, 3, 4 and 5 nodes. Running each set for 60 seconds, we measure how many edges are found for relevant paths. Figure 5 presents the results, where we see that with more entities specified by the user, we can ifnd more paths per unit time. The median number of path edges found in one minute varies from 24 to 194, with a median memory usage peaking at 7 GB for a single query. Applying the restriction that avoids expanding neighbours of nodes with degree greater than 100,000 increases the median number of path edges found in one minute to the range of 34 to 1,009, with a greatly reduced (× 70) median memory usage of 100 MB per query.
Usability In order to gain initial insights into the usability of the system, we created an online survey that asked user to perform two tasks: one is a guided navigation (where the entities for the search are provided), hinting in this case that they may find an interesting path and the other is a navigation where the user chooses the entities to search.
They then responded to a System Usability Scale (SUS) survey [17], rating ten claims about the system on a Likert scale from 1 (disagree) to 5 (agree). The SUS score ranges from 0–100, where a score of 68 is considered average [18]. A Spanish version of the survey was shared on a forum of students and professors at the University of Chile, receiving 82 responses. An English ES(82)
EN(15)
ALL(97) s
I found the various functions in this system were 4.26 well integrated.
I thought there was too much inconsistency in this system.
I would imagine that most people would learn to use this system very quickly.
I found the system very cumbersome to use.
I felt very confident using the system.
I needed to learn a lot of things before I could get 1.29 going with this system. m version was shared on the public Wikidata mailing list, receiving 15 responses.
Table 1 presents the mean and standard deviation of the responses for each claim of the SUS questionnaire, along with the SUS score. Considering all 97 respondents, the overall SUS score was 79.51 ± 14.62, which is considered better than average usability [18]. While users appreciate the speed at which paths are found, and the way that some such paths reveal interesting connections between entities of interest, they also commented that sometimes too many paths are displayed, making it dificult to read the graph.
WoolNet is an online system that enables users to find, filter and visualise paths between entities of interest in a knowledge graph. The system can be used for exploratory search, where some use-cases we envisage include finding potential collaborations between researchers or afiliations, identifying potential conflicts of interest, studying vectors of corruption, etc. We showed that by using our proposed indexing scheme and multi-source path finding algorithm, WoolNet is capable of finding tens or hundreds of paths per minute (in the median case) on a real-world knowledge graph consisting of 100 million nodes and 716 million edges. An evaluation with 97 users indicates that WoolNet’s usability is better than average.
The final system applies a number of practical heuristics to reduce the average cost of each request, such as limiting the maximum path length, avoiding the expansion of high-degree nodes, etc.; these heuristics could afect certain applications, and testing them in more detail would be an interesting subject for future work. Another next step would be to conduct a topology-based analysis of the performance of the algorithm considering the graph density, potentially using synthetic graphs, and also to explore adaptations to our algorithm that would allow for returning full paths between all pairs of nodes according to a particular semantics.
The online system (https://woolnet.dcc.uchile.cl) provides an end-to-end system. In terms of limitations and potential future improvements, WoolNet assumes the knowledge graph to be static, where in a future version we hope to support updates. It would also be of interest to explore the potential of multi-threading to improve performance, and to be able to configure the system to use popular graph databases as a back-end. In some cases, WoolNet can generate a great many paths, making it dificult to visually distinguish individual connections; we would like to provide users more powerful features to filter paths, and to explore measures and other heuristics that can help to filter paths that are unlikely to be of interest to a user.
We thank the anonymous users who took part in our survey for their time and feedback. We also thank the anonymous reviewers whose feedback helped to improve this work. This work was partly funded by ANID - Millennium Science Initiative Program - Code ICN17_002 and by FONDECYT Grant 1221926. [6] M. A. Rodriguez, The Gremlin graph traversal machine and language (invited talk), in: Proceedings of the 15th Symposium on Database Programming Languages, Pittsburgh, PA, USA, October 25-30, 2015, ACM, 2015, pp. 1–10. URL: https://doi.org/10.1145/2815072. 2815073. doi:10.1145/2815072.2815073. [7] W. W. W. Consortium, et al., Sparql 1.1 overview (2013). [8] O. Erling, Virtuoso, a Hybrid RDBMS/Graph Column Store, IEEE Data Eng. Bull. 35 (2012) 3–8. URL: http://sites.computer.org/debull/A12mar/vicol.pdf. [9] J. Webber, A programmatic introduction to Neo4j, in: SPLASH ’12, 2012. URL: https: //doi.org/10.1145/2384716.2384777. doi:10.1145/2384716.2384777. [10] B. Thompson, M. Personick, M. Cutcher, The Bigdata® RDF Graph Database, in: Linked
Data Management, Chapman and Hall/CRC, 2014, pp. 193–237. [11] B. R. Bebee, D. Choi, A. Gupta, A. Gutmans, A. Khandelwal, Y. Kiran, S. Mallidi, B. McGaughy, M. Personick, K. Rajan, et al., Amazon Neptune: Graph Data Management in the Cloud, in: ISWC (P&D/Industry/BlueSky), 2018. [12] R. Angles, M. Arenas, P. Barceló, A. Hogan, J. L. Reutter, D. Vrgoč, Foundations of Modern Query Languages for Graph Databases, ACM Comput. Surv. 50 (2017). URL: https://doi.org/10.1145/3104031. doi:10.1145/3104031. [13] M. Lissandrini, T. B. Pedersen, K. Hose, D. Mottin, Knowledge graph exploration: where are we and where are we going?, SIGWEB Newsl. 2020 (2020) 4:1–4:8. URL: https://doi. org/10.1145/3409481.3409485. doi:10.1145/3409481.3409485. [14] P. Heim, S. Hellmann, J. Lehmann, S. Lohmann, T. Stegemann, RelFinder: Revealing Relationships in RDF Knowledge Bases, in: 4th International Conference on Semantic and Digital Media Technologies (SAMT), volume 5887 of Lecture Notes in Computer Science, Springer, 2009, pp. 182–187. URL: https://doi.org/10.1007/978-3-642-10543-2_21. doi:10. 1007/978-3-642-10543-2\_21. [15] G. Tartari, A. Hogan, WiSP: Weighted Shortest Paths for RDF Graphs, in: Fourth International Workshop on Visualization and Interaction for Ontologies and Linked Data (VOILA@ISWC), volume 2187 of CEUR Workshop Proceedings, CEUR-WS.org, 2018, pp. 37–52. URL: https://ceur-ws.org/Vol-2187/paper4.pdf. [16] S. Malyshev, M. Krötzsch, L. González, J. Gonsior, A. Bielefeldt, Getting the Most Out of Wikidata: Semantic Technology Usage in Wikipedia’s Knowledge Graph, in: ISWC 2018, 2018. [17] J. R. Lewis, The system usability scale: past, present, and future, International Journal of
Human–Computer Interaction 34 (2018) 577–590. [18] J. Sauro, J. R. Lewis, Quantifying the user experience: Practical statistics for user research, Morgan Kaufmann, 2016.