Given two sets of entities - potentially the results of two queries on a knowledge-graph like YAGO or DBpedia- characterizing the relationship between these sets in the form of important people, events and organizations is an analytics task useful in many domains. In this paper, we present an intuitive and efficiently computable vertex centrality measure that captures the importance of a node with respect to the explanation of the relationship between the pair of query sets. Using a weighted link graph of entities contained in the English Wikipedia, we demonstrate the usefulness of the proposed measure.
Consider a journalist researching the political relations between France and Germany.
In order to gain insight into the underlying relationship, it is an important task to identify
entities (e. g. events, organizations, etc.) that play an important role in the interactions
between these countries. This task can be greatly simplified if the journalist could simply
input two sets of entities – corresponding to the classes “French Politicians” and
“German Politicians” – and the system automatically generates a ranking of entities in the
knowledge base, reflecting their potential for characterizing the relationship between the
two entity-sets. Variants of this relationship characterization problem can be found in
settings ranging from political studies to analysis of relationships in computational
biology and economics. With the availability of massive entity-relationship networks such as
Wikipedia, DBLP, and BioCyc networks as well as large Semantic Web ontologies like
YAGO2 [
In this paper, we develop a novel centrality measure called relationship centrality,
that assesses the ‘strength’ of a node in the relationship path between the given two
sets of nodes. These scores can be computed exactly, or can be well-approximated to
scale to networks as large as the entire Wikipedia graph, comprising tens of millions of
edges. The resulting rankings can further be restricted to entities of certain types (e.g,
Organization or Location etc.), leveraging semantic knowledge-bases such as
YAGO2 [
Graph centrality measures, which assign to every node a score reflecting its importance in
the graph structure, are a valuable tool for analyzing different kinds of graphs. Although
they have been studied extensively in the scope of social networks, the use of centrality
measures in the context of Semantic Web is gaining importance only recently. The
classical measures proposed in past include closeness [
In contrast, the measure we introduce in this work, called relationship centrality, is easier to compute since it is designed to assign scores that reflect the centrality only with respect to the two input entity sets, rather than on a global scale. Formally, given two query entity sets S and T from the network, we define the relationship centrality of a node v as follows: cR(v) = X X s2S t2T
1
(s; v; t)
;
where (s; v; t) is a penalty function for a path connecting a node s 2 S and t 2 T
passing through v, given by: (s; v; t) = (1 + d(s; v)) (1 + d(v; t)): The distance d( ; )
between two nodes connected by an edge can be customized based on the underlying
network to measure the semantic distance between the corresponding entities. The
corresponding edge-weighting schemes we envision can be based on the graph structure
(Milne-Witten inlink overlap measure [
Relationship centrality takes into account different paths than betweenness centrality (which regards the shortest paths between all pairs of vertices). For every vertex in the graph and every pair (s; t) 2 S T , the shortest path from s to t passing through v contributes to the centrality score of v.
The corresponding paths are computed as follows: For every vertex s 2 S and t 2 T , the shortest distances to each vertex v 2 V are computed using Dijkstra’s algorithm. Then, the centrality scores for every vertex can be computed from the resulting distance vectors. While the O(m + n log(n)) time complexity induced by each of the jSj + jT j required shortest path computations is rather lightweight, for very large graphs the corresponding computation time can be too demanding, especially for interactive applications. For this purpose, we have experimented with an alternative scoring scheme which only considers shortest path distances up to a value 2 R. Then, the distance from a query node q to a vertex v is approximated in the following way: d~(q; v) = (d(q; v) diam(G) for d(q; v) else, ; where diam(G) denotes the diameter of the (weighted) graph. In our experimental evaluation in Section 4, we evaluate the quality of computed scores based on different choices of the cutoff parameter, : 3
In this section, we briefly present the application scenarios we envision. We target analytical tasks at the downstream of Semantic Web applications. In particular, we consider a large knowledge-base (such as YAGO or DBPedia), over which S and T sets are derived as results of SPARQL queries.
Example: As a concrete scenario, the following two queries retrieve all organizations conducting research on (variants of) lung cancer, and all tobacco companies respectively: SELECT ?p WHERE f ?p <rdf:type> <Organization> . ?p <worksOn> <Lung Cancer> g
SELECT ?c WHERE f ?c <rdf:type> <American Tobacco Company> g
An analytics task could be to identify legal cases that played an important role in the relationship between the entity sets corresponding to the query results. We can utilize the relationship centrality measure developed above, and then use a type hierarchy, e. g. Wikipedia categories or the WordNet lexical database, to retain only the relevant entity types in the generated ranking. 4
In this section, we provide an overview over our experimental evaluation of the
relationship centrality measure. In order to empirically validate the assigned scores, we
have compiled several example queries over an edge-weighted entity-relationship graph
obtained from Wikipedia: The vertices of the graph correspond to Wikipedia pages
that represent an entity contained in the YAGO knowledge base. Two vertices u; v are
connected via a weighted, undirected edge if there exists an internal Wikipedia link in
either direction between the corresponding articles, A(u); A(v). The weight we assign
to the edge (u; v) should capture the semantic relatedness of the respective concepts. For
this purpose, we employ the inlink overlap measure originally proposed by Milne and
Witten [
log(n) log(minfjIuj; jIvjg) where Iu and Iv denote the set of pages linking to A(u) and A(v), respectively and n corresponds to the overall number of pages. The resulting weights lie in the interval [0; 1]. Using this measure, vertices u and v exhibit a high semantic relatedness if the weight of the edge (u; v) is close to zero. Finally, we discard all edges with d(u; v) 1. Q1 Q2 Q3 41,960.40 ms 18,629.80 ms 1.0 4,616.05 ms 0.55 48,174.80 ms 15,002.70 ms 1.0 5,117.02 ms 0.60 71,162.50 ms 32,028.50 ms 1.0 7,858.39 ms 0.87
Table 2. Computation time and ranking quality The resulting graph structure contains around 2.5 million vertices (entities) and roughly 37 million edges.
In order to empirically evaluate our ranking, we use three example queries where the sets of entities correspond to a collection of Q1: Events between European politicians (S) and US American politicians (T )4 Q2: Movies between US action movie stars (S) and Asian action movie stars (T )5 Q3: Events between countries from the Middle East/Central Asia (S) and Western countries (T )6 In Table 1 we present the top-10 ranked results by relationship centrality for each of the queries. The resulting rankings suggest that our measure is useful for the explanation of the relationship between the sets of query entities. Regarding the computation time, we give an overview over the effect of pruning the shortest path computation using different cutoff parameters , as well as the resulting rank correlation (measured by Kendall’s ) for the top 10 entities in Table 2. 5
In this work we have presented the relationship centrality measure, a vertex centrality score that reflects the potential of an individual vertex for the explanation of the relationship between two sets of query nodes. Our preliminary experimental results over the edge-weighted Wikipedia entity-relationship graph indicate that our measure can provide valuable insights into the relationship between sets of real-world entities. In future work, we plan to conduct a large-scale evaluation of our result ranking in a user study. In addition, we plan to use our centrality measure as a building block for extracting interesting subgraphs between the query entities.