MPI-I-2009-5-007

Many modern applications are faced with the task of knowledge discovery in large entity-relationship (ER) graphs, such as domain-specific knowledge bases or social networks. An important building block of many knowledge discovery tasks is that of finding the "closest" relationships between k >= 2 given entities. We have investigated this kind of knowledge discovery task in our previous work. A more general knowledge discovery scenario on ER graphs is that of mining the most "informative" subgraph for k(>= 2) given entities of interest (i.e. query entities). Intuitively, this would be the subgraph that best explains the relations between the k given query entities. This knowledge discovery scenario is more general than the one we have studied previously, in that its focus is on whole subgraphs (and not on trees). Furthermore, in this scenario, the semantics plays a crucial role. Our notion of informativeness has a rather intuitive flavor. Hence, we are interested in measures that capture the human intuition of an informative ER subgraph. An adequate measure should favor insightful and salient relationships between the query entities. Examples for such knowledge discovery tasks are queries that aim at finding the relations between k given biomedical entities, the connections between k criminals, the most relevant data shared by k Web 2.0 users, etc. In this work, we addresses this problem of mining most informative ER subgraphs. We define a framework for computing a new notion of informativeness of nodes. This is used for defining the informativeness of entire subgraphs. We present MING (for Mining INformative Graphs), a principled and efficient method for extracting the most informative subgraph for k(>=2) given query entities. The viability of our approach is demonstrated through experiments on real-life datasets, with comparisons to prior work.