Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


MING: Mining Informative Entity-Relationship Subgraphs

Kasneci, Gjergji and Weikum, Gerhard and Elbassuoni, Shady

MPI-I-2009-5-007. July 2009, 32 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2009-5-007.pdf493 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Kasneci, Gjergji and Weikum, Gerhard and Elbassuoni, Shady},
  TITLE = {MING: Mining Informative Entity-Relationship Subgraphs},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2009-5-007},
  MONTH = {July},
  YEAR = {2009},
  ISSN = {0946-011X},