Paper Info
Title
ESPRESSO: Explaining Relationships between Entity Sets
Abstract
Analyzing and explaining relationships between entities in a knowledge graph is a fundamental problem with many applications. Prior work has been limited to extracting the most informative subgraph connecting two entities of interest. This paper extends and generalizes the state of the art by considering the relationships between two sets of entities given at query time. Our method, coined ESPRESSO, explains the connection between these sets in terms of a small number of relatedness cores: dense sub-graphs that have strong relations with both query sets. The intuition for this model is that the cores correspond to key events in which entities from both sets play a major role. For example, to explain the relationships between US politicians and European politicians, our method identifies events like the PRISM scandal and the Syrian Civil War as relatedness cores. Computing cores of bounded size is NP-hard. This paper presents efficient approximation algorithms. Our experiments with real-life knowledge graphs demonstrate the practical viability of our approach and, through user studies, the superior output quality compared to state- of-the-art baselines.
Year
DOI
Venue
2016
10.1145/2983323.2983778
ACM International Conference on Information and Knowledge Management
Keywords
Field
DocType
knowledge graphs,relationships analysis,graph mining,graph querying,social networks
Small number,Espresso,Data mining,Approximation algorithm,Knowledge graph,Social network,Information retrieval,Computer science,Baseline (configuration management),Intuition,Bounded function
Conference
Citations 
PageRank 
References 
7
0.56
33
Authors
6
Name
Order
Citations
PageRank
Stephan Seufert170.56
Klaus Berberich2127168.96
Srikanta Bedathur360743.23
Sarath Kumar Kondreddi4111.68
Patrick Ernst5706.51
Gerhard Weikum6127102146.01