An important aspect of exploratory search over graph data is to understand what paths connect a given pair of nodes. Since the resulting paths can be manifold, various works propose ranking paths likely to be of interest to a user; these methods often rely on enumerating all such paths (up to a fixed length or number) before ranking is applied. In this paper, we instead propose applying a shortest path search on weighted versions of the graph in order to directly compute the most relevant path(s) between two nodes without fixed-length bounds, further obviating the need to enumerate irrelevant paths. We investigate weightings based on node degree, PageRank and edge frequency, contrasting the paths produced by these schemes over the Wikidata graph and discussing performance issues. Finally we conduct a user study over Wikidata where evaluators assess the quality of the paths produced; though inter-rater consensus on which paths are of most interest is low, we achieve statistically significant results to suggest that users find the weighted shortest paths more interesting than the baseline shortest paths without weights.
Though a wealth of data has been published as Linked Data using the Semantic
Web standards, we still lack techniques and tools by which non-expert users can
interact with graph-structured data [20]. A characteristic feature of interacting
with such graphs is the ability to query the connectivity of nodes through paths
of arbitrary length. Along these lines, a number of proposals have been made to
empower users to find such paths satisfying certain conditions, such as shortest
paths, or simple paths that do not revisit a node (or edge), or to find pairs of
nodes connected by paths satisfying regular expressions [
Hence further work has been conducted on ranking simple paths1 – paths not
repeating a node – that exist between the query nodes according to a variety of
metrics and methods [
In this paper, we thus propose to reformulate the problem of ranking simple paths to that of computing shortest paths in a weighted RDF graph;3 our core hypothesis is that we can design a weighting scheme for an RDF graph such that the shortest paths in the weighted version of the graph are of more interest to the user than in the non-weighted version (note that the weights only optionally form part of the output: the hypothesis considers “plain” paths being output).
The benefit of such a weighting scheme can be seen from two perspectives. First, with respect to ranking paths, simple paths of relevance to the user can be directly computed using well-known shortest path algorithms without having to explicitly enumerate a potentially exponential number of paths, and without a priori bounds on the length or number of paths considered. Second, with respect to shortest paths, a potentially factorial number of shortest paths can still exist between two nodes, where standard shortest path algorithms either return the first such path found, or return all shortest paths; a weighting scheme as we propose could thus be used to “break ties”, providing a more granular notion of (weighted) shortest path than considering path length alone.
In Figure 1, we provide a motivating example taken from the Wikidata knowledge graph [30]; note that for readability we present the example with node identifiers based on English labels (e.g., :film, :director) rather than Wikidata identifiers (e.g., :Q11424, :P57). Let us consider a user that wishes to find connections between the two theatrical movies :Blade Runner and :Top Gun. First we observe that paths should traverse edges in either direction; for example, we consider both :director and :directed−, returning the direction traversed in the output. Second, we consider simple paths that do not visit the same node twice since, otherwise, we would have potentially infinite paths with redundancy (e.g., jumping back and forth between the Scott brothers an arbitrary number of times). Thereafter, we can identify six simple paths: one stating that both movies are instance of :film, one stating that their country of origin is the :United States of America, and four indicating that they were directed by brothers (two paths for each direction of the :sibling relation and its inverse). Though the paths between the query nodes through :United States of America or :film have the shortest length, we argue that the longer path through the Scott brothers is more likely to be of interest to a user.
While many works propose to first enumerate all paths and thereafter rank
them to try find the most interesting ones, we rather propose to apply a weighting
to the graph in an off-line phase and then compute the shortest paths in the
weighted graph on-line. For example, one could imagine that high weights are
2 In a k-clique (k ≥ 2) with 2 directed labelled edges between each node pair, there
are 4l (k(−k−1−2)l!)! simple paths of length l (encoding edge labels and inverses) from any
node to any other; for l = k − 1, this gives 4k−1(k − 2)! simple paths.
3 A shortest path in a weighted graph has the lowest sum of node and edge weights.
:Blade Runner
assigned to high-centrality nodes such as :film and to frequent edges such as
:instance of; however, care needs to be taken since a naive weighting scheme
will lead to long paths through nodes representing relatively obscure entities: the
most specific or “improbable” paths are not always best. Furthermore, in other
cases, paths of interest may pass through high-centrality nodes, particularly if
the edge label is selective (e.g., :head of state). Hence designing an appropriate
weighting scheme requires balancing potentially numerous factors [
In this paper, we thus investigate methods by which we can compute simple paths that exist between two input nodes in a directed edge-labelled graph (such as an RDF graph) that are likely to be of relevance to a user. We reduce the ranking problem to that of weighting the nodes and edges of the graph prior to applying a shortest-path algorithm. We evaluate various weighting schemes over the Wikidata graph, comparing the paths that they produce and their performance at various scales, further conducting a user study where evaluators assess the weighted shortest paths given by the various weighting schemes. Outline: The following section presents related works while Section 3 introduces preliminaries. Section 4 presents our weighting schemes and implementation. Turning to evaluation, Section 5 compares statistics for the paths generated by each scheme over Wikidata, while Section 6 presents the results of a user study. Section 7 concludes and discusses future work. 2
Perhaps the most prominent way to traverse paths in RDF graphs is through
the property paths feature of the SPARQL query standard, which allows users
to find pairs of nodes connected by paths that conform to a specified regular
expression; such features are common amongst query languages designed for
graphs [
On the other hand, a number of works have proposed methods to find paths between nodes in RDF graphs. RelFinder [14, 15, 21] finds paths between two nodes indexed by a SPARQL endpoint by issuing a sequence of queries looking for successively longer paths; while this approach has the benefit of being portable across endpoints, the types of paths that can be found are limited by the use of SPARQL (which cannot return paths) and no ranking is applied.
Recognising that the number of paths between two nodes can exceed the
user’s capacity to comprehend, a wide variety of works have been proposed to
rank paths – called semantic associations, semantic relationships, complex
relationships, etc. – between nodes. A seminal work is SemRank [
Other approaches have looked at various problems and applications relating
to computing shortest paths for RDF graphs (e.g, [
We now present preliminaries relating to RDF graphs, paths and weights.
RDF graphs: Given pairwise disjoint sets of IRIs (I), literals (L) and blank nodes
(B), an RDF triple (s, p, o) is an element of I ∪ B × I × I ∪ B ∪ L, where s is the
subject, p predicate and o object. A set of RDF triples G is called an RDF graph,
owing to the fact that one can view each triple as a directed labelled edge s −→p o,
and hence an RDF graph can be viewed as a directed edge-labelled graph [
The main goal of this work is to investigate weighting schemes for RDF graphs such that the shortest paths by weight between two nodes are deemed to be of more interest to users than shortest paths by length. Such a scheme would then allow us to compute paths of interest to a user in a best-first manner using shortest path algorithms without having to enumerate all simple paths or having to implement a priori bounds on the length or number of paths considered.
As discussed previously, a wide variety of metrics and approaches have been
defined for ranking enumerated simple paths that we can adapt for weighting
schemes [
While our approach will offer various computational benefits and does not require fixed thresholds, since we consider weighted shortest graphs, we are more limited in terms of the ranking functions we can express. More specifically, towards defining such a weighting scheme for an RDF graph G, we are left to instantiate the functions ωV : V → R≥0 and ωP : P → R≥0 introduced previously for weighting the nodes and edge-labels of the graph. Under our framework, we consider sums of weights on individual nodes/edges, which (currently) rules out adopting measures such as homogeneity that consider the diversity of all edges/nodes. Furthermore, we note that there is some redundancy in the above measures, where for example frequency, informativeness and specificness offer different versions of the same underlying principle: how common is a given edge/path. With these considerations, we propose the following weighting schemes. Length ( l): We consider as a baseline a weighting scheme where ωV : V → {1} and ωP : P → {1}, setting the weights of all edges and nodes to a fixed constant. This configuration thus produces a shortest path according to length and is equivalent to not considering any weights (on nodes or edges).
Centrality ( d,p): In order to weight nodes, we consider two measures of
centrality mentioned by Cheng et al. [
Hybrid: The above schemes may be complementary, dealing respectively with
path length, node weights and edge weights. For example, if we consider node
centrality alone, the paths produced may tend to be very long, visiting various
relatively obscure nodes; furthermore, in Figure 2, we would not be able to
distinguish common/uncommon edges to a high-centrality node. Hence we propose
a number of hybrid schemes. The first weighting scheme combines the
centralitybased node weights and length. We first linearly normalise both ωV functions to
produce scores in the interval [
We now present the results of some experiments of applying our weighted shortest path methods to the Wikidata graph [30]. Wikidata is a collaboratively-edited knowledge base where data relevant to Wikipedia can be curated and managed by human editors. We select Wikidata for our experiments as it is a large graph and – being edited by thousands of users, as well as covering a broad domain of interest – exhibits a high degree of diversity in terms of the types of nodes and edges described, the nature of the relations expressed, and so forth. Thus Wikidata’s size poses a non-trivial test of the scalability of our method, while its diversity poses a challenge to the generality of our weightings.
The questions we wish to address with this initial study are as follows: – How is performance affected by scale and weighting scheme? – How do the paths produced by different weighting schemes differ? Data: We perform experiments over the “truthy” version of Wikidata from the 2017-06-07 dump; the truthy version does not include qualifiers or references and selects preferred values for properties (e.g., including only the most recent population for a city). For performance experiments, we define sub-graphs of Wikidata at varying scales: observing that numeric Qx IDs are defined in chronological order, where the earliest nodes (often important entities such as countries, prominent persons, etc.) have lower numeric IDs, we set limits on x of 1,600,000, 3,200,000, 6,400,000, 12,800,000. Thereafter, we select all triples (s, p, o) such that both s and o have Qx IDs below the limit for x. We apply no limit on property Qy IDs and we do not consider edges involving literals or blank nodes. Since IDs are not “dense” in Wikidata, where entities may be removed, applying a limit of 1,600,000 may not result in precisely that number of nodes in the resulting graph. Table 1 presents the number of nodes and edges in each sub-graph used, where the full dataset represents the full graph. Machine: The machine used for all experiments has 2× Intel Xeon Quad Core E5-2609 V3 CPUs (@1.9GHz), 32GB of RAM, and 2× 2TB Seagate 7200 RPM 32MB Cache SATA hard-disks in a RAID-1 configuration. 8 A demo is available at http://wisp.dcc.uchile.cl over a Wikidata sub-graph of 1.2 million nodes; we do not use the full graph for performance reasons discussed later. Queries: To generate our first set of queries (Q1), from each dataset, we randomly select 100 pairs of entities. Since pairs selected from larger datasets may not appear in smaller datasets, we also generate a second set common to all graphs (Q2): we randomly select 100 pairs of entities with ID less than 100,000. Configurations: We selected l (baseline), d, dl, del, p, pl and pel for testing. Each configuration returns the first shortest path found.
Performance by weights: In Figure 3, we present box-plots of response times for finding a shortest path over the full graph with the selected weighting schemes and Q1. We can see that the averages and medians are above 27 seconds in all cases, and that the baseline shortest path algorithm is the fastest. The slowest weighting scheme (del) is almost twice as slow, taking almost a minute, on average, for each query. Investigating further, for the baseline l scheme, 12.3 million nodes (49% of all nodes) are visited, on average, to answer a query pair; on the other hand, when vertex weights are considered, more nodes are visited, where, for example, p visits 15.2 million nodes (61%), on average.
Performance by scale: The previous experiments suggest that finding shortest paths is a costly process, where a large number of nodes in the graph need to be visited and where the query times may thus exceed a minute in some cases for the full graph. We are thus interested to see how scale affects the performance. In Figure 4, we present the response times for Q2; for reasons of space, we present results for del – the slowest strategy in the previous results – though other strategies followed a similar pattern. We highlight that as the size of each dataset doubles, the mean response times likewise roughly double; an exception is for the full dataset, which although more than double the size of the 12.8 m dataset, sees an increase of only ∼1.2× in mean query times, where the average ratio of nodes visited drops from 29% to 23%. Note that we selected Q2 since we wish to compare different scales for the same set of queries; we also ran Q1 at all scales for del, where the mean times for 6.4 m, 12.8 m and full increase to 13.5 s, 34.0 s, and 53.7 s, respectively: nodes randomly sampled from the larger graphs generate longer paths requiring more nodes to be visited. Comparing weighted shortest paths: Next we look to see if different weighting schemes do in fact generate different paths. In Figure 5, we provide a heat-map that indicates for each pair of weighting schemes the percentage of the 100 Q1 paths generated over the full dataset that coincide with another weighting scheme. In terms of the pairs of schemes producing the most similar results, we l d see that del and pel produce the same paths for 83% of the queries, with pl and dl coinciding for 71% of queries; however d and p have much lower overlap: 13%. To help explain this observation, in Figure 6 we present an overview of the lengths of paths produced by each scheme; notably d and p produce much longer paths on average since their weights are less affected by length, where longer paths are naturally much less likely to coincide. On the other hand, even though all *l measures tend to have short paths, we note that all weighted graphs tend to vary in their results from the baseline l (particularly d and p, which produce much longer paths). Finally, we observe a notable difference in dl and del (56% overlap) and between pl and pel (54% overlap), suggesting that the introduction of edge weights significantly affects the paths computed. 6
In the previous section we discussed results on the performance of the path computation at different scales and for different weighting schemes; we also presented a statistical analysis of the differences between the paths produced by such schemes, noting that most schemes vary considerably, particularly from the baseline where only the length of the path is considered. In this section, we present a user study whose goal is to address our main research question: – Do users prefer shortest paths in weighted versions of the graph (d*, p*) versus shortest paths by length only (l)?
Although a number of related datasets have been proposed for evaluating
paths and entity relatedness (e.g., by Cheng et al. [
Scoring: To facilitate the evaluation of the paths, we created a version of the system that would display paths generated by all weighting schemes for a given query on one page. Instructions to users were minimal: they were asked to evaluate the path on a Likert scale with seven levels indicating how interesting the path was as an explanation for how the two entities were connected, scoring each generated path from 1 (worst), to 7 (best); other than that, scoring was left to the user’s discretion. Displaying all paths for one query on the same page allowed users to consider paths produced by the other schemes when making their evaluation. The evaluators were 10 students from a Semantic Web course. To avoid long response times (see Figure 4), we used the 1.6 m dataset.
Best (mean: 6; 2 evaluations: {5, 7}): :Saturn
:child astronomic body :Titan (moon) :named after :Titan (deity) :named after :HMS Titanic
Worst (mean: 1.25; 4 evaluations: {1, 1, 1, 2}): :Lionel Messi Evaluations: In total, 81 query evaluations were recorded, of which 79 were complete (2 incomplete evaluations were discarded). In total, we thus gathered an average of ∼4 evaluations for each query pair, totalling 79 × 7 = 553 scores for paths on a scale of 1–7. As an example, in Figure 7 we present the best (:Saturn,:HMS Titanic) and worst (:Lionel Messi,:Stephen Curry) evaluated paths for which we received multiple evaluations.
Inter-rater agreement: Given that we use an ordinal scale for evaluations, we
apply a correlation measure to assess inter-rater agreement: specifically we use
Kendall’s τ -b measure.9 For each query pair, we measured the τ -b correlation
between each distinct pair of evaluations across strategies, and then took the mean
for each query; then taking the mean over all queries, the result was a
macroaveraged correlation of τ = 0.201, indicating positive but slight agreement. We
believe this low correlation to be due to two main factors: (1) the subjective
nature of the evaluation, where rather than providing specific instructions on how
to rate paths (which may bias towards one strategy or another), we left users
to decide their own criteria for rating; (2) we did not verify beforehand that
interesting paths did indeed exist for the query entities, and so it may be the
case that there is no clear “better” paths in some cases. To address this point,
we consider two query sets for our results: the set of All queries as previously
described; and a set of Concordant queries, intended to represent queries for
which there was inter-rater consensus, defined as query pairs with multiple
evaluations and a positive (τ -b) correlation; the latter sub-set contains 8 query pairs,
with τ = 0.552 and a total of 27 × 7 = 189 scores for individual paths.
Comparing evaluations of weighted shortest paths: In Figure 8, we present a
high-level comparison of the mean evaluations of All queries and the subset of
Concordant queries for different weighting schemes. We present these results
considering (1) queries involving entities of the same type, (2) queries involving
entities of different types, (3) the combination of both. As a general trend, we see
that the paths tended to have mean evaluations tending towards the (neutral)
middle of the Likert scale. Furthermore, we see that the mean evaluations in the
9 Kendall’s τ -b is a non-parametric rank coefficient measuring correlation between two
lists of values in a range of [
Same types Different types Both
Same types
Different types
Both
W.S.
p d dl del p pl pel Concordant set tend to be slightly lower than the All set, which suggests slightly more agreement on which paths are bad (per Figure 7). Returning to our main research question, the baseline without weights (l) had the worst mean evaluations in all results; to the right of Figure 8, we present the significance of the difference of the mean for each weighting scheme to the baseline, where for All we see that the mean evaluations of d, del, p, pl and pel are significantly different (α = 0.05) from the baseline; only the mean evaluation of the dl paths was not significantly different from that of l where, in Figure 5, we observed that dl has the most similar paths to l. For the Concordant set, though fewer evaluations are available (n = 27) significant results were still achieved for d, del, and pl.10 In summary, though the hybrid weighting schemes we propose do not show any clear benefit to those based solely on node centrality, the results 10 An interesting case is p, which achieved the second-highest mean, but did not reach significance: analysing the result further, p had a much lower Pearson correlation with l than other configurations, leading to the higher p-value. show that users preferred weighted shortest paths over the unweighted baseline, with the results being significant in many cases.
Materials and Demo: We make code, queries, performance results, ratings, etc., available at https://github.com/GTartari/Weighted-Shortest-Paths. A demo over a subset of Wikidata (1.6 m) is available at http://wisp.dcc.uchile.cl/. 7
In this paper, we proposed to apply weightings to RDF graphs such that the weighted shortest paths produced are of more interest to the user than shortest paths based on length alone. The goal of such an approach is to enable the application of best-first search algorithms – such as Dijkstra’s algorithm – to directly find and output the paths of most interest, avoiding fixed bounds. We then proposed a number of weighting schemes for RDF graphs based on path length, node centrality, and edge-label frequency, as well as combinations thereof.
With an efficient implementation based on Dijkstra’s algorithm layered on top of in-memory graph traversal indexes, we showed that the approach can scale to the full Wikidata graph (25 million nodes, 90 million edges); however, response times increase linearly with scale, where queries on the full dataset (which must visit 12.3–14.5 million nodes) can take in the order of a minute; on the other hand, for a sub-graph of 1.2 million nodes and 6.6 million edges, queries can be executed in the order of 2–4 seconds. We further noted that the proposed weighting schemes can increase mean response times, requiring more nodes to be visited. We also observed that most weighting schemes produce largely disjoint results, though we found large overlap between the dl–pl and del–pel schemes.
Finally, we presented a user study over Wikidata designed to address the main research question: are the weighted shortest paths of more interest to a typical user than the baseline shortest paths considering only length? We found that the user scoring of paths in general exhibited a low, positive inter-rater correlation, implying that the task of scoring paths is, in general, highly subjective; however, there was a positive consensus for a subset of the chosen queries. Thereafter we found that all weighting schemes outperformed the baseline in this evaluation, and that the results were significant (α = 0.05) in most cases. This contributes evidence to validate our main hypothesis that appropriate weighting schemes can improve the perceived relevance of shortest paths for users.
Future work: There are many important directions left to be explored. A
limitation of our current work is the performance over large graphs: while we see
it as a positive to be able to scale to the full Wikidata graph, response times
in the order of a minute would preclude interactive response times and test the
patience of users; we believe that the best way to tackle this issue is with
approximations, or perhaps using an appropriate heuristic with A*-search. Another
limitation is that our methods currently only produce one path, though
adaptations of Dijkstra-style algorithms do exists for top-k paths, including in an RDF
setting [
Another area for improvement is with respect to evaluation: trying to evaluate
which paths are of interest to users is challenging given the subjective nature of
the task and the number of possible paths to choose from, precluding the creation
of a reliable and complete gold standard [
Semantic Web. In: 7th Extended Semantic Web Conference. pp. 303–317 (2010) 16. Herrera, J.E.T., Casanova, M.A., Nunes, B.P., Leme, L.A.P.P., Lopes, G.R.: An entity relatedness test dataset. In: International Semantic Web Conference (ISWC). pp. 193–201 (2017) 17. Hertling, S., Schro¨der, M., Jilek, C., Dengel, A.: Top-k shortest paths in directed labeled multigraphs. In: SemWebEval Challenge at ESWC. pp. 200–212 (2016) 18. Hulpu¸s, I., Prangnawarat, N., Hayes, C.: Path-Based Semantic Relatedness on Linked Data and Its Use to Word and Entity Disambiguation. In: International Semantic Web Conference (ISWC). pp. 442–457 (2015) 19. J¨amsen, J., Niemi, T., Ja¨rvelin, K.: Derived types in semantic association discovery.
J. Intell. Inf. Syst. 35(2), 213–244 (2010) 20. Karger, D.R.: The Semantic Web and end users: What’s wrong and how to fix it.
IEEE Internet Computing 18(6), 64–70 (2014) 21. Lehmann, J., Schu¨ppel, J., Auer, S.: Discovering unknown connections – the DBpedia relationship finder. In: Social Semantic Web (CSSW). pp. 99–110 (2007) 22. Nunes, B.P., Herrera, J.E.T., Taibi, D., Lopes, G.R., Casanova, M.A., Dietze, S.: SCS connector – quantifying and visualising semantic paths between entity pairs.
In: The Semantic Web (ESWC) Satellite Events. pp. 461–466 (2014) 23. Partl, C., Gratzl, S., Streit, M., Wassermann, A.M., Pfister, H., Schmalstieg, D., Lex, A.: Pathfinder: Visual Analysis of Paths in Graphs. Comput. Graph. Forum 35(3), 71–80 (2016) 24. Pirr`o, G.: Explaining and Suggesting Relatedness in Knowledge Graphs. In: International Semantic Web Conference (ISWC). pp. 622–639 (2015) 25. Rusu, D., Fortuna, B., Mladenic, D.: Measuring concept similarity in ontologies using weighted concept paths. Applied Ontology 9(1), 65–95 (2014) 26. Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J.
Comput. 8(3), 410–421 (1979) 27. Vidal, M., Rivera, J.C., Iba´n˜ez, L.D., Raschid, L., Palma, G., Rodr´ıguez-Drumond, H., Ruckhaus, E.: An authority-flow based ranking approach to discover potential novel associations between Linked Data. Semantic Web 5(1), 23–46 (2014) 28. Viswanathan, V., Krishnamurthi, I.: Ranking semantic relationships between two entities using personalization in context specification. Inf. Sci. 207, 35–49 (2012) 29. Viswanathan, V., Krishnamurthi, I.: Finding relevant semantic association paths using semantic ant colony optimization algorithm. Soft Comput. 19(1), 251–260 (2015) 30. Vrandecic, D., Kro¨tzsch, M.: Wikidata: a free collaborative knowledgebase. Commun. ACM 57(10), 78–85 (2014) 31. Zhang, Y., Cheng, G., Qu, Y.: Towards exploratory relationship search: A clustering-based approach. In: Joint International Conference on Semantic Technology (JIST). pp. 277–293 (2013)