Computing interesting paths
between resources on the Web

What makes a pattern interesting?

• DBpedia contains 31,404,445 unique topics,
  1,840,598 (5.9%) of which are people.
  • The chance that two random things are people is only 0.3%.
  • Given this rareness, why were you not impressed?
• The goal of this class is to find interesting paths between two subjects in a knowledge base.
  • pathfinding
  • knowledge
  • interestingness

Pathfinding and its applications

• Pathfinding is a well-studied problem in graph theory.
• Pathfinding has several important applications:
  • constructing roads and utilities
  • automating industrial robots
  • discovering relatedness between biological molecules
• We will discuss two widely used algorithms:
  • Dijkstra
  • A*

The Dijkstra algorithm

• inputs
  • a graph G = (V, E)
  • vertex source ∈ V and vertex target ∈ V
  • a function weight(e) for each edge e ∈ E
• output
  • a sequence S of connected edges from source to target
• complexity
  • time: O(|V| log |V| + |E|) using a priority queue

The Dijkstra algorithm

• for each vertex v ∈ U (a copy of V)
  • dist[v] ← ∞ if v ≠ source, 0 otherwise
• while U is not empty
  • v ← u ∈ U with minimal dist[u], removing u from U
  • for each edge e = (v, n) ∈ E
    • if dist[n] > dist[v] + weight(e)
      • dist[n] ← dist[v] + weight(e)
      • prev[n] ← v
  • terminate if v = target, reconstructing S using prev

The Dijkstra algorithm

The A* algorithm

• inputs
  • like Dijkstra: graph G, source, target, function weight
  • a heuristic function goalDistance(v) for each vertex v ∈ V
    • to find the actual shortest path, should never overestimate
• output
  • a sequence S of connected edges from source to target
• complexity
  • time: O(|E|)

The A* algorithm

• A* maintains an investigation set of relevant vertices.
  • when visiting a vertex, all its neighbours are added
• Instead of Dijkstra's minimal distance from source,
  we use the estimated distance to the target.
• We strive to have a monotonic goalDistance,
  since then each vertex needs at most one visit.
  • neighbours that are more expensive to reach
    also have higher goalDistance values

The A* algorithm

Resource Description Framework

• RDF offers the basic building blocks
  to represent large-scale, distributed knowledge.
• An RDF dataset contains RDF triples,
  consisting of a subject, predicate, and object.
  • subjects, predicates, and objects can be reused
    within and across datasets
• We can view RDF triples as a graph.
  • subjects and objects are vertices
  • predicates are edges

An RDF example

// Declare reusable identifiers
PREFIX dbp: <http://dbpedia.org/resource/>
PREFIX dbo: <http://dbpedia.org/ontology/>

// Define RDF triples
dbp:Elvis_Presley  dbo:birthDate  "1935-01-08"^^xsd:date.
dbp:Elvis_Presley  dbo:birthPlace  dbp:Mississippi.
dbp:Oprah_Winfrey  dbo:birthPlace  dbp:Mississippi.
dbp:Oprah_Winfrey  dbo:residence   dbp:Chicago.

An RDF example

DBpedia knowledge base

• DBpedia is a large-scale RDF graph,
  extracted from Wikipedia infoboxes.
  • a topic's key-value pairs become triples
  • DBpedia 2015 contains 400 million triples
• DBpedia allows us to connect
  real-world topics via paths.
  • major challenge:
    pathfinding with 400 million edges

The SPARQL query language

• RDF databases provide the SPARQL query language.
  • retrieve triples based on specific patterns
• SPARQL is not practical for pathfinding.
  • difficult to prioritize certain predicates over others
  • difficult to express paths of arbitrary length
• Pathfinding queries are computationally hard.
  • a SPARQL engine evaluates queries using joins
  • pathfinding would need large joins, and they are expensive

Tailoring A* to our problem

• Our graph consists of 400 million edges.
• How will we find interesting paths?
  • We have to adjust the weight function to prefer rare edges.
• How will we find paths fast?
  • We have to choose an effective and efficient goalDistance.

Choosing a weight function

• We consider an edge e(start, end) interesting if:
  • start has a low probability of being reached randomly
  • end has a low probability of being reached randomly
• We therefore define weight as follows:
  • degree(v) = | { e(x, y) ∈ E | x = v } |
  • predicateScore(e) = % of triples using the same predicate
  • weight(e(v, u)) = log(degree(v) + degree(u)) × predicateScore(e)

Choosing a goalDistance heuristic

• A vertex brings us closer to the target
  if they are semantically related.
  • similar things are often expressed in similar ways
  • we can estimate relatedness based on common predicates
  • the Jaccard distance compares the similarity of sets
• We therefore define goalDistance as follows:
  • $\mathrm{goalDistance(v,\; u)}=1–\frac{|\mathrm{predicates(v)}\bigcap \mathrm{predicates(u)}|}{|\mathrm{predicates(v)}\bigcup \mathrm{predicates(u)}|}$

Calculate a path

• from to Calculate

Visualization of an example path

To remember from this class

• Pathfinding can connect items in knowledge bases.
  • interpret large-scale RDF datasets as regular graphs
• To boost interestingness, prefer rare nodes and links.
  • choose weight function as the inverse of number of links
  • prioritize rare types of links over others
• To speed up, use semantic distance as heuristic.
  • choose a distance metric (such as Jaccard)
  • choose relevant node characteristics (such as predicates)