Searching and browsing relationships between entities is an important task in many domains. To support users in interactively exploring a large set of relationships, we present a novel relationship search engine called RelClus, which automatically groups search results into a dynamically generated hierarchy with meaningful labels. This hierarchical clustering of relationships exploits their schematic patterns and a similarity measure based on information theory.
Many information needs in various domains can be met by using an information
system that supports searching and browsing relationships (a.k.a. associations)
between entities, which are represented as paths in RDF graph. Whereas path
finding has been efficiently implemented (e.g. [
RelClus is based on the DBpedia data set (dbpedia.org), and consists of four components: keyword mapping, path finding, relationship clustering, and result presentation, which will be detailed in the following. 1 http://ws.nju.edu.cn/relclus/. User interaction starts with two keyword phrases, e.g. Sydney and Melbourne in Fig. 1, describing two entities between which the relationships are requested. Featured by the autocomplete functionality implemented based on Apache Lucene (lucene.apache.org), RelClus can help the user conveniently determine the mapping from keyword phrases to entities. In addition, when necessary, the user can change the default length limit on the relationships to be returned, by choosing an appropriate value from the drop-down list next to the search button. 2.2
Once the search button is clicked, RelClus will start to find all the paths (subject to a length limit) between the two entities specified by the user. In particular, edges in a relationship are not required to go the same direction because the inverse of a property also has meaning for human readers. Figure 2 illustrates an RDF graph containing five relationships, R1–R5, from Sydney to Melbourne, as our running example.
Paths are found by using bidirectional breadth-first search (bi-BFS), which runs two simultaneous searches from the two entities given and finds paths when the two meet in the middle. According to our experimental results, bi-BFS is generally faster than a single BFS or DFS, though requiring more memory than DFS. To further reduce the time needed, our bi-BFS runs concurrently in multiple threads. Besides, a cache is used to avoid repeated path finding for repeated queries in the future. 2.3
As a key step of RelClus, all the relationships found by bi-BFS will be clustered into a hierarchy. For simplicity, the relationships are firstly grouped by length, (R1) residence (R2) Lleyton Hewitt Sydney deathPlace (R3) and then each group is processed individually. We will illustrate our clustering algorithm by using R1–R5 in Fig. 2, all of which are of length three.
Our clustering algorithm follows an agglomerative manner; that is, each relationship starts in its own cluster, and a hierarchy of clusters is built by progressively merging the most similar pair of clusters.
Before describing the similarity measure, we need to introduce how we assign a meaningful and representative label to each cluster. The label of a cluster is a relationship pattern, which is a high-level abstraction of relationships where the nodes can be either entities or classes, and the directions of edges are omitted; the label of a singleton cluster is just the unique relationship it contains. For instance, in Fig. 3, R4 labels the singleton cluster {R4}; P1 is a relationship pattern that labels the cluster {R4; R5}, where ⊤P denotes the top property that is a superproperty of all the properties.
We call P1 a superpattern of R4 and R5 in the sense that for each entity, class,
and property in R4 and R5, the element in the corresponding position in P1
is either the same or its type, superclass, and superproperty, respectively; in
particular, it is the least common element among the possibilities. For instance,
Leslie Cody in R4 and William Bowrey in R5 are instances of both Person and
Athlete, and we choose Athlete in P1 because it is the least common type given
Athlete being a subclass of Person, and thus contains the most information
content as discussed in [
We define the similarity between two clusters as the information content associated with the relationship pattern that labels their union, which indicates how many commonalities the two clusters share. The information content associated with a relationship pattern is the sum of the information contents of its elements. So, at the beginning of the clustering process in our running example, {R4} and {R5} are merged before {R1} and {R2} because the label of {R4; R5}, which would be P1, contains more information content than P2 which would label {R1; R2}, mainly because P2 contains one more top property, the information content of which is trivially zero.
In addition, after successively forming {R4; R5} labeled with P1 and {R1; R2} labeled with P2, we will immediately merge {R1; R2} and {R3} into {R1; R2; R3}, still labeled with P2, because R3 also matches this pattern. Finally, the two
Sydney
P
PopulatedPlace P
clusters labeled with P1 and P2 are merged into the root cluster labeled with P3, and a hierarchy is formed. A hierarchical clustering is visualized as a collapsible/expandable tree, as illustrated in Fig. 1. Each entity is prefixed by a thumbnail if available; each class is prefixed by some; the top property is omitted; and the top class is shown as something. Each non-singleton cluster is suffixed by its size in parentheses, and sibling clusters are sorted by their sizes decreasingly.
Acknowledgments. This work was supported in part by the NSFC under Grant 61100040 and 61223003, and in part by the JSNSF under Grant BK2012723.