MPI-I-2009-5-007
MING: Mining Informative Entity-Relationship Subgraphs
Kasneci, Gjergji and Weikum, Gerhard and Elbassuoni, Shady
July 2009, 32 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-2009-5-007.pdf (493 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2009-5-007
BibTeX
@TECHREPORT{KasneciWeikumElbassuoni2009,
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},
}