AMIE: Association Rule Mining under Incomplete Evidence
in Ontological Knowledge Bases
Luis Galárraga
1
, Christina Teflioudi
1
, Katja Hose
2
, Fabian M. Suchanek
1
1
Max-Planck Institute for Informatics, Saarbrücken, Germany
2
Aalborg University, Aalborg, Denmark
1
{lgalarra, chteflio, suchanek}@mpi-inf.mpg.de,
2
{khose}@cs.aau.dk
ABSTRACT
Recent advances in information extraction have led to huge
knowledge bases (KBs), which capture knowledge in a ma-
chine-readable format. Inductive Logic Programming (ILP)
can be used to mine logical rules from the KB. These rules
can help deduce and add missing knowledge to the KB.
While ILP is a mature field, mining logical rules from KBs is
different in two aspects: First, current rule mining systems
are easily overwhelmed by the amount of data (state-of-the
art systems cannot even run on today’s KBs). Second, ILP
usually requires counterexamples. KBs, however, implement
the open world assumption (OWA), meaning that absent
data cannot be used as counterexamples. In this paper, we
develop a rule mining model that is explicitly tailored to
support the OWA scenario. It is inspired by association rule
mining and introduces a novel measure for confidence. Our
extensive experiments show that our approach outperforms
state-of-the-art approaches in terms of precision and cover-
age. Furthermore, our system, AMIE, mines rules orders of
magnitude faster than state-of-the-art approaches.
Categories and Subject Descriptors
H2.8 [Information Systems]: Database Applications
General Terms
Algorithms
Keywords
Rule Mining, Inductive Logic Programming, ILP
1. INTRODUCTION
In recent years, we have experienced the rise of large
knowledge bases (KBs), such as Cyc [23], YAGO [35], DB-
pedia [5], and Freebase
1
. These KBs provide information
about a great variety of entities, such as people, countries,
rivers, cities, universities, movies, animals, etc. Moreover,
KBs also contain facts relating these entities, e.g., who was
born where, which actor acted in which movie, or which city
is located in which country. Today’s KBs contain millions
of entities and hundreds of millions of facts.
Yet, even these large KBs are not complete. Some of
them are extracted from natural language resources that
1
http://freebase.com
inevitably exhibit gaps. Others are created and extended
manually. Making these KBs complete requires great effort
to extract facts, check them for correctness, and add them
to the KB. However, KBs themselves often already contain
enough information to derive and add new facts. If, for in-
stance, a KB contains the fact that a child has a mother,
then the mother’s husband is most likely the father:
motherOf (m, c) ∧ marriedTo(m, f ) ⇒ fatherOf (f, c)
As for any rule, there can be exceptions, but in the vast
majority of cases, the rule will hold. Finding such rules
can serve four purposes: First, by applying such rules on
the data, new facts can be derived that make the KB more
complete. Second, such rules can identify potential errors
in the knowledge base. If, for instance, the KB contains the
statement that a totally unrelated person is the father of a
child, then maybe this statement is wrong. Third, the rules
can be used for reasoning. Many reasoning approaches rely
on other parties to provide rules (e.g., [27, 31]). Last, rules
describing general regularities can help us understand the
data better. We can, e.g., find out that countries often trade
with countries speaking the same language, that marriage is
a symmetric relationship, that musicians who influence each
other often play the same instrument, and so on.
The goal of this paper is to mine such rules from KBs.
We focus on RDF-style KBs in the spirit of the Seman-
tic Web, such as YAGO [35], Freebase
1
, and DBpedia [5].
These KBs provide binary relationships in the form of RDF
triples
2
. Since RDF has only positive inference rules, these
KBs contain only positive statements and no negations. Fur-
thermore, they operate under the Open World Assumption
(OWA). Under the OWA, a statement that is not contained
in the KB is not necessarily false; it is just unknown. This
is a crucial difference to many standard database settings
that operate under the Closed World Assumption (CWA).
Consider an example KB that does not contain the infor-
mation that a particular person is married. Under CWA we
can conclude that the person is not married. Under OWA,
however, the person could be either married or single.
Mining rules from a given dataset is a problem that has
a long history. It has been studied in the context of asso-
ciation rule mining and inductive logic programming (ILP).
Association rule mining [3] is well-known in the context of
sales databases. It can find rules such as “If a client bought
beer and wine, then he also bought aspirin”. The confidence
of such a rule is the ratio of cases where beer and wine was
actually bought together with aspirin. Association rule min-
ing inherently implements a closed world assumption: A rule
2
http://www.w3.org/TR/rdf-primer/
Copyright is held by the International World Wide Web Conference
Committee (IW3C2). IW3C2 reserves the right to provide a hyperlink
to the author’s site if the Material is used in electronic media.
WWW 2013, May 13–17, 2013, Rio de Janeiro, Brazil.
ACM 978-1-4503-2035-1/13/05.
413
