kLog: A Language for Logical and Relational Learning
with Kernels
Paolo Frasconia,c,∗, Fabrizio Costab,c , Luc De Raedtc , Kurt De Gravec

arXiv:1205.3981v5 [cs.AI] 28 Jul 2014

a

Dipartimento di Ingegneria dell’Informazione, Università degli Studi di Firenze, via di
Santa Marta 3, I-50139 Firenze, Italy
b
Institut für Informatik, Albert-Ludwigs-Universität, Georges-Koehler-Allee, Geb 106,
D-79110 Freiburg, Germany
c
Departement Computerwetenschappen, KU Leuven, Celestijnenlaan 200A,
B-3001 Heverlee, Belgium

Abstract
We introduce kLog, a novel approach to statistical relational learning. Unlike
standard approaches, kLog does not represent a probability distribution directly. It is rather a language to perform kernel-based learning on expressive
logical and relational representations. kLog allows users to specify learning
problems declaratively. It builds on simple but powerful concepts: learning
from interpretations, entity/relationship data modeling, logic programming,
and deductive databases. Access by the kernel to the rich representation
is mediated by a technique we call graphicalization: the relational representation is first transformed into a graph — in particular, a grounded entity/relationship diagram. Subsequently, a choice of graph kernel defines the
feature space. kLog supports mixed numerical and symbolic data, as well
as background knowledge in the form of Prolog or Datalog programs as in
inductive logic programming systems. The kLog framework can be applied
to tackle the same range of tasks that has made statistical relational learning
so popular, including classification, regression, multitask learning, and collective classification. We also report about empirical comparisons, showing
I

PF was a visiting professor at KU Leuven and FC a postdoctoral fellow at KU Leuven
while this work was initiated
∗
Corresponding author
Email addresses: p-f@dsi.unifi.it (Paolo Frasconi),
costa@informatik.uni-freiburg.de (Fabrizio Costa), Luc.DeRaedt@cs.kuleuven.be
(Luc De Raedt), Kurt.DeGrave@cs.kuleuven.be (Kurt De Grave)

Preprint submitted to Artificial Intelligence

July 29, 2014

that kLog can be either more accurate, or much faster at the same level of
accuracy, than Tilde and Alchemy. kLog is GPLv3 licensed and is available
at http://klog.dinfo.unifi.it along with tutorials.
Keywords: Logical and relational learning, Statistical relational learning,
kernel methods, Prolog, Deductive databases
1. Introduction
The field of statistical relational learning (SRL) is populated with a fairly
large number of models and alternative representations, a state of affairs often
referred to as the “SRL alphabet soup” [1, 2]. Even though there are many
differences between these approaches, they typically extend a probabilistic
representation (most often, a graphical model) with a logical or relational
one [3, 4]. The resulting models then define a probability distribution over
possible worlds, which are typically (Herbrand) interpretations assigning a
truth value to every ground fact.
However, the machine learning literature contains — in addition to probabilistic graphical models — several other types of statistical learning methods. In particular, kernel-based learning and support vector machines are
amongst the most popular and powerful machine learning systems that exist
today. But this type of learning system has — with a few notable exceptions
to relational prediction [5, 6] — not yet received a lot of attention in the
SRL literature. Furthermore, while it is by now commonly accepted that
frameworks like Markov logic networks (MLNs) [7], probabilistic relational
models (PRMs) [8], or probabilistic programming [3, 4] are general logical
and relational languages that support a wide range of learning tasks, there
exists today no such language for kernel-based learning. It is precisely this
gap that we ultimately want to fill.
This paper introduces the kLog language and framework for kernel-based
logical and relational learning. The key contributions of this framework are
threefold: 1) kLog is a language that allows users to declaratively specify
relational learning tasks in a similar way as statistical relational learning and
inductive logic programming approaches but it is based on kernel methods
rather than on probabilistic modeling; 2) kLog compiles the relational domain and learning task into a graph-based representation using a technique
called graphicalization; and 3) kLog uses a graph kernel to construct the
feature space where eventually the learning takes place. This whole process
2

is reminiscent of knowledge-based model construction in statistical relational
learning. We now sketch these contributions in more detail and discuss the
relationships with statistical relational learning.
One contribution of this paper is the introduction of the kLog language
and framework for kernel-based logical and relational learning. kLog is embedded in Prolog (hence the name) and allows users to specify different types
of logical and relational learning problems at a high level in a declarative way.
kLog adopts, as many other logical and relational learning systems, the learning from interpretations framework [9]. In this way, the entities (or objects)
and the relationships amongst them can be naturally represented. However,
unlike typical statistical relational learning frameworks, kLog does not employ a probabilistic framework but is rather based on linear modeling in a
kernel-defined feature space.
kLog constitutes a first step into the direction of a general kernel-based
SRL approach. kLog generates a set of features starting from a logical and
relational learning problem and uses these features for learning a (linear)
statistical model. This is not unlike Markov logic but there are two major
differences. First, kLog is based on a linear statistical model instead of
a Markov network. Second, the feature space is not immediately defined
by the declared logical formulae but it is constructed by a graph kernel,
where nodes in the graph correspond to entities and relations, some given in
the data, and some (expressing background knowledge) defined declaratively
in Prolog. Complexity of logical formulae being comparable, graph kernels
leverage a much richer feature space than MLNs. In order to learn, kLog
essentially describes learning problems at three different levels. The first
level specifies the logical and relational learning problem. At this level, the
description consists of an E/R-model describing the structure of the data
and the data itself, which is similar to that of traditional SRL systems [10].
The data at this level is then graphicalized, that is, the interpretations are
transformed into graphs. This leads to the specification of a graph learning
problem at the second level. Graphicalization is the equivalent of knowledgebased model construction. Indeed, SRL systems such as PRMs and MLNs
also (at least conceptually) produce graphs, although these graphs represent
probabilistic graphical models. Finally, the graphs produced by kLog are
turned into feature vectors using a graph kernel, which leads to a statistical
learning problem at the third level. Again there is an analogy with systems
such as Markov logic as the Markov network that is generated in knowledgebased model construction lists also the features. Like in these systems, kLog
3

features are tied together as every occurrence is counted and is captured by
a single same parameter in the final linear model.
It is important to realize that kLog is a very flexible architecture in which
only the specification language of the first level is fixed; at this level, we employ an entity/relationship (E/R) model. The second level is then completely
determined by the choice of the graph kernel. In the current implementation of kLog that we describe in this paper, we employ the neighborhood
subgraph pairwise distance kernel (NSPDK) [11] but the reader should keep
in mind that other graph kernels can be incorporated. Similarly, for learning the linear model at level three we mainly experimented with variants of
SVM learners but again it is important to realize that other learners can
be plugged in. This situation is akin to that for other statistical relational
learning representations, for which a multitude of different inference and
learning algorithms has been devised (see also Section 8 for a discussion of
the relationships between kLog and other SRL systems).
In the next section, we illustrate the main steps of kLog modeling with a
complete example in a real world domain. In Section 3, we formalize the assumed statistical setting for supervised learning from interpretations, provide
some background on statistical modeling from a relational learning point of
view, and position kLog more clearly in the context of related systems such
as Markov logic, M3 N [6], etc. In Section 4, we formalize the semantics of the
language and illustrate what types of learning problems can be formulated in
the framework. Further examples are given in Section 5. The graphicalization approach and the graph kernel are detailed in Section 6. Some empirical
evaluation is reported in Section 7 and, finally, the relationships to other SRL
systems are discussed in Section 8.
2. A kLog example
Before delving into the technical details of kLog, we illustrate the different
steps on a real-life example using the UW-CSE dataset prepared by Domingos et al. for demonstrating the capabilities of MLNs [7]. Anonymous data
was obtained from the University of Washington Department of Computer
Science and Engineering. Basic entities include persons (students or professors), scientific papers, and academic courses. Available relations specify,
e.g., whether a person was the author of a certain paper, or whether he/she
participated in the teaching activities of a certain course. The learning task

4

consists of predicting students’ advisors, i.e., to predict the binary relation
advised_by between students and professors.
2.1. Data format
Data comes in the form of true ground atoms, under the closed-world assumption. Since (first-order logic) functions are not allowed in the language,
a ground atom is essentially like a tuple in a relational database, for example
taught_by(course170,person211,winter_0102).
kLog learns from interpretations. This means that the data is given as a
set of interpretations (or logical worlds) where each interpretation is a set of
ground atoms which are true in that world. In this example there are five
interpretations: ai, graphics, language, systems, and theory, corresponding to
different research groups in the department. For instance, a fragment of the
interpretation ai is shown in Listing 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

advised_by(person21,person211).
advised_by(person45,person211).
has_position(person211,faculty).
has_position(person407,faculty).
in_phase(person14,post_generals).
in_phase(person21,post_generals).
in_phase(person284,post_quals).
in_phase(person45,post_generals).
professor(person211).
professor(person407).
publication(title110,person14).
publication(title110,person407).
publication(title25,person21).
publication(title25,person211).
publication(title25,person284).
publication(title25,person407).
publication(title44,person211).
publication(title44,person415).
publication(title44,person45).
student(person14).
student(person21).
student(person284).
student(person45).
ta(course12,person21,winter_0203).
ta(course24,person21,spring_0203).
ta(course24,person70,autumn_0304).
taught_by(course12,person211,autumn_0001).
taught_by(course143,person211,winter_0001).
taught_by(course170,person211,winter_0102).
taught_by(course24,person211,autumn_0102).
taught_by(course24,person211,spring_0203).
taught_by(course24,person407,spring_0304).
taught_by(course82,person407,winter_0102).

Listing 1: Database D for the UW-CSE domain
All ground atoms in a particular interpretation together form an instance
of a relational database and the overall data set consists of several (disjoint)
5

student_id

phase

position

in_phase

has_position

student

advisee

advised_by

advisor

professor

prof_id

Figure 1: E/R diagram for the UW-CSE domain.

databases.
2.2. Data modeling and learning
The first step in kLog modeling is to describe the domain using a classic
database tool: entity relationship diagrams. We begin by modeling two entity
sets: student and professor, two unary relations: in_phase and has_position,
and one binary relation: advised_by (which is the target in this example).
The diagram is shown in Figure 1. The kLog data model is written using the
fragment of code of Listing 2.
1
2
3
4

signature has_position(professor_id::professor, position::property )::extensional.
signature advised_by(p1::student, p2::professor)::extensional.
signature student(student_id::self)::extensional.
signature professor(professor_id::self)::extensional.

Listing 2: Examples of signature declaration.
Every entity or relationship that kLog will later use to generate features
(see feature generation below) is declared by using the special keyword signature. Signatures are similar to the declarative bias used in inductive logic
programming systems. There are two kinds of signatures, annotated by the
reserved words extensional and intensional. In the extensional case, all ground
atoms have to be listed explicitly in the data file; in the intensional case,
ground atoms are defined implicitly using Prolog definite clauses. A signature has a name and a list of arguments with types. A type is either the
name of an entity set (declared in some other signature) or the special type
property used for numerical or categorical attributes. In the ground atoms,
6

constants that are not properties are regarded as identifiers and are simply
used to connect ground atoms (these constants disappear in the result of the
graphicalization procedure explained below).1
One of the powerful features of kLog is its ability to introduce novel relations using a mechanism resembling deductive databases. Such relations are
typically a means of injecting domain knowledge. In our example, it may
be argued that the likelihood that a professor advises a student increases if
the two persons have been engaged in some form of collaboration, such as
co-authoring a paper, or working together in teaching activities. In Listing 3
we show two intensional signatures for this purpose. An intensional signature
declaration must be complemented by a predicate (written in Prolog) which
defines the new relation. When working on a given interpretation, kLog asserts all the true ground atoms in that interpretation in the Prolog database
and collects all true groundings for the predicate associated with the intensional signature. Intensional signatures can also be effectively exploited to
1
2
3
4

5
6
7
8

9
10
11
12
13

signature on_same_course(s::student,p::professor)::intensional.
on_same_course(S,P) :professor(P), student(S),
ta(Course,S,Term), taught_by(Course,P,Term).
signature on_same_paper(s::student,p::professor)::intensional.
on_same_paper(S,P) :student(S), professor(P),
publication(Pub, S), publication(Pub,P).
signature n_common_papers(s::student,p::professor,n::property )::intensional.
n_common_papers(S,P,N) :student(S), professor(P),
setof(Pub, (publication(Pub, S), publication(Pub,P)), CommonPapers),
length(CommonPapers,N).

Listing 3: Intensional signatures and associated Prolog predicates.
introduce aggregated attributes [9]. The last signature in Listing 3 shows for
example how to count the number of papers a professor and a student have
1

The special type name self is used to denote the name of the signature being declared,
as in lines 7–8 of Listing 2. Thus, a signature containing an argument of type self introduces
a new entity set while other signatures introduce relationships.

7

in_phase(post_generals)

student
person284

has_position(faculty)

p1
in_phase(post_quals)

p1

p1
advised_by
student
person45

p1

p1

p1
p0

on_same_paper

p1

on_same_paper

p0

professor
person211

p0

p0
p0

on_same_paper

advised_by

p0

professor
person407

p0

p1

student
person14

on_same_course
on_same_paper

p0

p1

p0
p1

p1

p1

has_position(faculty)

p1

in_phase(post_generals)

on_same_paper

in_phase(post_generals)

on_same_paper
p1

student
person21

p1

Figure 2: Graphicalization on the tiny data set in the running example. Identifiers (such
as person45) are only shown for the sake of clarity; kLog does not use them to generate
features.

published together.
2.3. Graphicalization
Graphicalization is our approach to capture the relational structure of the
data by means of a graph. It enables the use of kernel methods in SRL via
a graph kernel, which measures the similarity between two graphs. The procedure maps a set of ground atoms into a bipartite undirected graph whose
nodes are true ground atoms and whose edges connect an entity atom to a
relationship atom if the identifier of the former appears as an argument in
the latter. The graph resulting from the graphicalization of the ai interpretation is shown in Figure 22 . It is from this graph that kLog will generate
propositional features (based on a graph kernel) for use in the learning procedure. The details of the graphicalization procedure and the kernel are given
in Sections 6 and 6.2, respectively.
Now that we have specified the inputs to the learning system, we still need
to determine the learning problem. This is declared in kLog by designating
2

Note that interpretation predicates which exist in the data but have not a corresponding signature (e.g., publication) do not produce nodes in the graph. However these
predicates may be conveniently exploited in the bodies of the intensional signatures (e.g.,
on_same_paper refers to publication).

8

one (or more) signature(s) as target (in this domain, the target relation is
advised_by). Several library predicates are designed for training, e.g., kfold
performs a k-fold cross validation. These predicates accept a list of target
signatures which specifies the learning problem.
3. Statistical setting
Our general approach to construct a statistical model is based on the
learning from interpretations setting [9]. An interpretation, or logical world,
is a set of ground atoms z. We assume that interpretations are sampled
identically and independently from a fixed and unknown distribution D. We
denote by {zi ; i ∈ I} the resulting data set, where I is a given index set
(e.g., the first n natural numbers) that can be thought of as interpretation
identifiers. Like in other statistical learning systems, the goal is to use a
data sample to make some form of (direct or indirect) inference about this
distribution.
For the sake of simplicity, throughout this paper we will mainly focus
on supervised learning. In this case, it is customary to think of data as
consisting of two separate portions: inputs (called predictors or independent
variables in statistics) and outputs (called responses or dependent variables).
In our framework, this distinction is reflected in the set of ground atoms in
a given interpretation. That is, z is partitioned into two sets: x (input or
evidence atoms) and y (output or query atoms).
The goal of supervised learning in this setting is to construct a prediction
function f that maps the set of input atoms x (a partial interpretation)
into a set of output atoms f (x). To this end, a feature vector3 φ(x, y) is
associated with each complete interpretation z = (x, y). A potential function
based on the linear model F (x, y) = w> φ(x, y) is then used to “score” the
interpretation. Prediction (or inference) is the process of maximizing F with
respect to y, i.e. f (x) = arg maxy F (x, y). Learning is the process of fitting
w to the available data, typically using some statistically motivated loss
function that measures the discrepancy between the prediction f (xi ) and the
observed output yi on the i-th training interpretation. This setting is related
to other kernel-based approaches to structured output learning (e.g., [12]),
which may be developed without associating a probabilistic interpretation to
F.
3

Our approach for constructing feature vectors is explained in Section 6.

9

The above perspective covers a number of commonly used algorithms
ranging from propositional to relational learning. To see this, consider first
binary classification of categorical attribute-value data. In this case, models
such as naive Bayes, logistic regression, and support vector machines (SVM)
can all be constructed to share exactly the same feature space. Using indicator functions on attribute values as features, the three models use a hyperplane as their decision function: f (x) = arg maxy∈{false,true} w> φ(x, y) where
for naive Bayes, the joint probability of (x, y) is proportional to exp(w> φ(x, y)).
The only difference between the three models is actually in the way w is fitted to data: SVM optimizes a regularized functional based on the hinge loss
function, logistic regression maximizes the conditional likelihood of outputs
given inputs (which can be seen as minimizing a smoothed version of the
SVM hinge loss), and naive Bayes maximises the joint likelihood of inputs
and outputs. The last two models are often cited as an example of generativediscriminative conjugate pairs because of the above reasons [13].
When moving up to a slightly richer data type like sequences (perhaps
the simplest case of relational data), the three models have well known extensions: naive Bayes extends to hidden Markov models (HMMs), logistic
regression extends to conditional random fields (CRFs) [14], and SVM extends to structured output SVM for sequences [15, 12]. Note that when
HMMs are used in the supervised learning setting (in applications such as
part-of-speech tagging) the observation x is the input sequence, and the states
form the output sequence y (which is observed in training data). In the simplest version of these three models, φ(x, y) contains a feature for every pair
of states (transitions) and a feature for every state-observation pair (emissions). Again, these models all use the same feature space (see, e.g., [14] for
a detailed discussion).
When moving up to arbitrary relations, the three above models can again
be generalized but many complications arise, and the large number of alternative models suggested in the literature has originated the SRL alphabet
soup mentioned at the beginning of the paper. Among generative models, one
natural extension of HMMs is stochastic context free grammars [16], which
in turn can be extended to stochastic logic programs [17]. More expressive
systems include probabilistic relational models (PRMs) [8] and Markov logic
networks (MLNs) [7], when trained generatively. Generalizations of SVM for
relational structures akin to context free grammars have also been investigated [12]. Among discriminative models, CRFs can be extended from linear
chains to arbitrary relations [14], for example in the form of discriminative
10

Table 1: Relationship among some statistical relational learning models.

Propositional
Sequences
General relations
Naive Bayes
HMM
Generative MLN
Logistic regression CRF
Discriminative MLN
SVM
SVM-HMM M3 N
Markov networks [18] and discriminative Markov logic networks [7]. The use
of SVM-like loss functions has also been explored in max-margin Markov networks (M3 N) [6]. These models can cope with relational data by adopting a
richer feature space. kLog contributes to this perspective as it is a language
for generating a set of features starting from a logical and relational learning
problem and using these features for learning a (linear) statistical model.
Table 1 shows the relationships among some of these approaches. Methods on the same row use similar loss functions, while methods in the same
column can be arranged to share the same feature space. In principle, kLog
features can be used with any loss.
4. The kLog language
A kLog program consists of:
• a set of ground facts, embedded in a standard Prolog database, representing the data of the learning problem (see, e.g., Listing 1);
• a set of signature declarations (e.g., Listing 2);
• a set of Prolog predicates associated with intensional signatures (e.g.,
Listing 3);
• a standard Prolog program which specifies the learning problem and
makes calls to kLog library predicates.
4.1. Data modeling and signatures
In order to specify the semantics of the language, it is convenient to formalize the domain of the learning problem as a set of constants (objects) C
and a finite set of relations R. Constants are partitioned into a set of entity
identifiers E (or identifiers for short) and set of property values V. Identifiers are themselves partitioned into k entity-sets E1 , . . . , Ek . A ground atom
11

r(c1 , . . . , cn ) is a relation symbol (or predicate name) r of arity n followed
by an n-tuple of constant symbols ci . An interpretation (for the learning
problem) is a finite set of ground atoms.
The signature for a relation r/m ∈ R is an expression of the form
r(name1 :: type1 , . . . , namem :: typem ) :: level
where, for all j = 1, . . . , m, typej ∈ {E1 , . . . , Ek , V} and namej is the name of
the j-th column of r. If column j does not have type V, then its name can
optionally include a role field using the syntax namej @rolej . If unspecified,
rolej is set to j by default. The level of a signature is either intensional or
extensional. In the extensional case, all the atoms which contribute to every
interpretation are those and only those listed in the data. In the intensional
case, ground atoms are those which result from the Prolog intensional predicates using Prolog semantics (optionally with tabling). In this way, users
may take advantage of many of the extensions of definite clause logic that
are built into Prolog.
The ability to specify intensional predicates through clauses (see an example in Listing 3) is most useful for introducing background knowledge in
the learning process and common practice in inductive logic programming
[9]. As explained in Section 6.2, features for the learning process are derived from a graph whose vertices are ground facts in the database; hence
the ability to declare rules that specify relations directly translates into the
ability to design and maintain features in a declarative fashion. This is a key
characteristic of kLog and, in our opinion, one of the key reasons behind the
success of related systems like Markov logic.
In order to ensure the well-definedness of the subsequent graphicalization
procedure (see Section 6), we introduce two additional database assumptions.
First, we require that the primary key of every relation consists of the columns
whose type belongs to {E1 , . . . , Ek } (i.e., purely of identifiers). This is perhaps
the main difference between the kLog and the E/R data models. As it will
become more clear in the following, identifiers are just placeholders and are
kept separate from property values so that learning algorithms will not rely
directly on their values to build a decision function4 .
The relational arity of a relation is the length of its primary key. As a
4

To make an extreme case illustrating the concept, it makes no sense to predict whether
a patient suffers from a certain disease based on his/her social security number.

12

special case, relations of zero relational arity are admitted and they must
consist of at most a single ground atom in any interpretation5 . Second, for
every entity-set Ei there must be a distinguished relation r/m ∈ R that
has relational arity 1 and key of type Ei . These distinguished relations are
called E-relations and are used to introduce entity-sets, possibly with (m−1)
attached properties as satellite data. The remaining |R| − k relations are
called R-relations or relationships 6 , which may also have properties. Thus,
primary keys for R-relations are tuples of foreign keys.
4.2. Supervised learning jobs
A supervised learning job in kLog is specified as a set of relations. We
begin defining the semantics of a job consisting of a single relation. Without
loss of generality, let us assume that this relation has signature
r(name1 :: Ei(1) , . . . , namen :: Ei(n) , namen+1 :: V, . . . , namen+m :: V)

(1)

with i(j) ∈ {1, . . . , k} for j = 1, . . . , n. Conventionally, if n = 0 there are
no identifiers and if m = 0 there are no properties. Recall that under our
assumptions the primary key of r must consist of entity identifiers (the first
n columns). Hence, n > 0 and m > 0 implies that r represents a function
with domain Ei(1) × · · · × Ei(n) and range V m . If m = 0 then r can be seen as
a function with a Boolean range.
Having specified a target relation r, kLog is able to infer the partition
x ∪ y of ground atoms into inputs and outputs in the supervised learning
setting. The output y consists of all ground atoms of r and all ground atoms
of any intensional relation r0 which depends on r. The partition is inferred
by analyzing the dependency graphs of Prolog predicates defining intensional
relations, using an algorithm reminiscent of the call graph computation in
ViPReSS [19].
We assume that the training data is a set of complete interpretations7 .
During prediction, we are given a partial interpretation consisting of ground
atoms x, and are required to complete the interpretation by predicting output
5

This kind of relations is useful to represent global properties of an interpretation (see
Example 5.1).
6
Note that the word “relationship” specifically refers to the association among entities
while “relation” refers the more general association among entities and properties.
7
kLog could be extended to deal with missing data by removing the closed world
assumption and requiring some specification of the actual false groundings.

13

ground atoms y. For the purpose of prediction accuracy estimation, we will
be only interested in the ground atoms of the target relation (a subset of y).
Several situations may arise depending on the relational arity n and the
number of properties m in the target relation r, as summarized in Table 2.
When n = 0, the declared job consists of predicting one or more properties
of an entire interpretation, when n = 1 one or more properties of certain
entities, when n = 2 one or more properties of pairs of entities, and so on.
When m = 0 (no properties) we have a binary classification task (where
positive cases are ground atoms that belong to the complete interpretation).
Multiclass classification can be properly declared by using m = 1 with a categorical property, which ensures mutual exclusiveness of classes. Regression is
also declared by using m = 1 but in this case the property should be numeric.
Note that property types (numerical vs. categorical) are automatically inferred by kLog by inspecting the given training data. An interesting scenario
occurs when m > 1 so that two or more properties are to be predicted at
the same time. A similar situation occurs when the learning job consists of
several target relations. kLog recognizes that such a declaration defines a
multitask learning job. However having recognized a multitask job does not
necessarily mean that kLog will have to use a multitask learning algorithm
capable of taking advantage of correlations between tasks (like, e.g., [20]).
This is because, by design and in line with the principles of declarative languages, kLog separates “what” a learning job looks like and “how” it is solved
by applying a particular learning algorithm. We believe that the separation
of concerns at this level permits greater flexibility and extendability and facilitates plugging-in alternative learning algorithms (a.k.a. kLog models) that
have the ability to provide a solution to a given job.
4.3. Implementation
kLog is currently embedded in Yap Prolog [21] and consists of three main
components: (1) a domain-specific interpreter, (2) a database loader, and (3)
a library of predicates that are used to specify the learning task, to declare
the graph kernel and the learning model, and to perform training, prediction,
and performance evaluation. The domain-specific interpreter parses the signature declarations (see Section 4.1), possibly enriched with intensional and
auxiliary predicates. The database loader reads in a file containing extensional ground facts and generates a graph for each interpretation, according
to the procedure detailed in Section 6. The library includes common utilities
for training and testing. Most of kLog is written in Prolog except feature
14

Table 2: Single relation jobs in kLog.

# of properties, m
0

1

>1

0
Binary
classification of interpretations
Multiclass / regression on interpretations
Multitask on interpretations

Relational arity, n
1

2

Binary
classification of entities

Link prediction

Multiclass / regression on entities

Attributed link prediction

Multitask predictions on entities

Multitask
attributed link prediction

vector generation and the statistical learners, which are written in C++.
kLog incorporates LibSVM [22] and Stochastic gradient descent [23] and can
interface with arbitrary (external) SVM solvers by coding appropriate data
conversion wrappers.
5. Examples
In Section 2 we have given a detailed example of kLog in a link prediction
problem. The kLog setting encompasses a larger ensemble of machine learning scenarios, as detailed in the following examples, which we order according
to growing complexity of the underlying learning task.
Example 5.1. [Classification of independent interpretations] This is the
simplest supervised learning problem with structured input data and scalar
(unstructured) output. For the sake of concreteness, let us consider the problem of small molecule classification as pioneered in the relational learning
setting in [24]. This domain is naturally modeled in kLog as follows. Each
molecule corresponds to one interpretation; there is one E-relation, atom,
that may include properties such as element and charge; there is one relationship of relational arity 2, bond, that may include a bond_type property
to distinguish among single, double, and resonant chemical bonds; there is
finally a zero-arity relationship, active, distinguishing between positive and
negative interpretations. A concrete example is given in Section 7.1.
Example 5.2. [Regression and multitask learning] The above example about
small molecules can be extended to the case of regression where the task is
15

to predict a real-valued property associated with a molecule, such as its biological activity or its octanol/water partition coefficient (logP) [25]. Many
problems in quantitative structure-activity relationships (QSAR) are actually formulated in this way. The case of regression can be handled simply by
introducing a target relation with signature activity(act::property).
If there are two or more properties to be predicted, one possibility is
to declare several target relations, e.g., we might add logP(logp::property).
Alternatively we may introduce a target relation such as:
target_properties(activity::property,logp::property).
Multitask learning can be handled trivially by learning independent predictors; alternatively, more sophisticated algorithms that take into account
correlations amongst tasks (such as [26]) could be used.
Example 5.3. [Entity classification] A more complex scenario is the collective classification of several entities within a given interpretation. We
illustrate this case using the classic WebKB domain [27]. The data set consists of Web pages from four Computer Science departments and thus there
are four interpretations: cornell, texas, washington, and wisconsin. In this
domain there are two E-relations: page (for webpages) and link (for hypertextual links). Text in each page is represented as a bag-of-words (using
the R-relation has) and hyperlinks are modeled by the R-relations link_to
and link_from. Text associated with hyperlink anchors is represented by the
R-relation has_anchor.
The goal is to classify each Web page. There are different data modeling
alternatives for setting up this classification task. One possibility is to introduce several unary R-relations associated with the different classes, such as
course, faculty, project, and student. The second possibility is to add a property to the entity-set page, called category, and taking values on the different
possible categories. It may seem that in the latter case we are just reifying
the R-relations describing categories. However there is an additional subtle
but important difference: in the first modeling approach it is perfectly legal
to have an interpretation where a page belongs simultaneously to different
categories. This becomes illegal in the second approach since otherwise there
would be two or more atoms of the E-relation page with the same identifier.
From a statistical point of view, since pages for the same department are
part of the same interpretation and connected by hyperlinks, the corresponding category labels are interdependent random variables and we formally have
16

an instance of a supervised structured output problem [28], that in this case
might also be referred to as collective classification [18]. There are however
studies in the literature that consider pages to be independent (e.g., [29]).
Example 5.4. [One-interpretation domains] We illustrate this case on the
Internet Movie Database (IMDb) data set. Following the setup in [30], the
problem is to predict “blockbuster” movies, i.e., movies that will earn more
than $2 million in their opening weekend. The entity-sets in this domain are
movie, studio, and individual. Relationships include acted_in(actor::individual,
m::movie), produced(s::studio, m::movie), and directed(director::individual, m::movie).
The target unary relation blockbuster(m::movie) collects positive cases. Training in this case uses a partial interpretation (typically movies produced before
a given year). When predicting the class of future movies, data about past
movies’ receipts can be used to construct features (indeed, the count of blockbuster movies produced by the same studio is one of the most informative
features [31]).
A similar scenario occurs for protein function prediction. Assuming data
for just a single organism is available, there is one entity set (protein) and a
binary relation interact expressing protein-protein interaction [32, 33].
6. Graphicalization and feature generation
The goal is to map an interpretation z = (x, y) into a feature vector
φ(z) = φ(x, y) ∈ F (see Section 3). This enables the application of several
supervised learning algorithms that construct linear functions in the feature
space F. In this context, φ(z) can be either computed explicitly or defined
implicitly, via a kernel function K(z, z 0 ) = hφ(z), φ(z 0 )i. Kernel-based solutions are very popular, sometimes computationally faster, and can exploit
infinite-dimensional feature spaces. On the other hand, explicit feature map
construction may offer advantages in our setting, in particular when dealing with large scale learning problems (many interpretations) and structured
output tasks (exponentially many possible predictions). Our framework is
based on two steps: first an interpretation z is mapped into an undirected
labeled graph Gz ; then a feature vector φ(z) is extracted from Gz . Alternatively, a kernel function on pairs of graphs K(z, z 0 ) = K(Gz , Gz0 ) could be
computed. The corresponding potential functionP
is then defined directly as
>
F (z) = w φ(z) or as a kernel expansion F (z) = i ci K(z, zi ).

17

The use of an intermediate graphicalized representation is novel in the
context of propositionalization, a well-known technique in logical and relational learning [9] that transforms graph-based or relational data directly into
an attribute-value learning format, or possibly into a multi-instance learning
one8 . This typically results in a loss of information, cf. [9]. Our approach
transforms the relational data into an equivalent graph-based format, without
loss of information. After graphicalization, kLog uses the results on kernels
for graph-based data to derive an explicit high-dimensional feature-based
representation. Thus kLog directly upgrades these graph-based kernels to
a fully relational representation. Furthermore, there is an extensive literature on graph kernels and virtually all existing solutions can be plugged
into the learning from interpretations setting with minimal effort. This includes implementation issues but also the ability to reuse existing theoretical
analyses. Finally, it is notationally simpler to describe a kernel and feature
vectors defined on graphs, than to describe the equivalent counterpart using
the Datalog notation.
The graph kernel choice implicitly determines how predicates’ attributes
are combined into features.
6.1. Graphicalization procedure
Given an interpretation z, we construct a bipartite graph Gz ([Vz , Fz ], Ez )
as follows (see Appendix B for notational conventions and Figure 2 for an
example).
Vertices: there is a vertex in Vz for every ground atom of every E-relation,
and there is a vertex in Fz for every ground atom of every R-relation.
Vertices are labeled by the predicate name of the ground atom, followed
by the list of property values. Identifiers in a ground atom do not
appear in the labels but they uniquely identify vertices. The tuple
ids(v) denotes the identifiers in the ground atom mapped into vertex
v.
Edges: uv ∈ Ez if and only if u ∈ Vz , v ∈ Fz , and ids(u) ⊂ ids(v). The edge
uv is labeled by the role under which the identifier of u appears in v
(see Section 4.1).
8
In multi-instance learning [34], the examples are sets of attribute-value tuples or sets
of feature vectors.

18

Note that, because of our data modeling assumptions (see Section 4.1), the
degree of every vertex v ∈ Fz equals the relational arity of the corresponding R-relation. The degree of vertices in Vz is instead unbounded and may
grow really large in some domains (e.g., social networks or World-Wide-Web
networks). The graphicalization process can be nicely interpreted as the
unfolding of an E/R diagram over the data, i.e., the E/R diagram is a template that is expanded according to the given ground atoms (see Figure 2).
There are several other examples in the literature where a graph template
is expanded into a ground graph, including the plate notation in graphical
models [35], encoding networks in neural networks for learning data structures [36], and the construction of Markov networks in Markov logic [7]. The
semantics of kLog graphs for the learning procedure is however quite different and intimately related to the concept of graph kernels, as detailed in the
following section.
6.2. Graph kernel
Learning in kLog is performed using a suitable graph kernel on the graphicalized interpretations. While in principle any graph kernel can be employed,
there are several requirements that the chosen kernel has to meet in practice. On the one hand, computational efficiency is very important, both
with respect to the number of graphs, and with respect to the graph size, as
the grounding phase in the graphicalization procedure can yield very large
graphs. On the other hand, we need a general purpose kernel with a flexible bias to adapt to a wide variety of application scenarios. In the case of
independent interpretations (as in Examples 5.1 and 5.2), any graph kernel
(several exist in the literature, see e.g. [37, 38, 39, 40, 41, 11, 42] and references therein) can be directly applied to the result of the graphicalization
procedure since there is exactly one graph for each interpretation. However,
when the task requires to make predictions about tuples of entities within the
same interpretation (as in Section 2 or in Examples 5.3 and 5.4) an immediate
application of existing graph kernels (such as those in the above references) is
not straightforward. Additionally, if the graph has vertices with large degree
(as in Example 5.3), kernels based on hard subgraph matching may severely
overfit the data.
In the current implementation, we use an extension of NSPDK [11]. While
the original kernel is suitable for sparse graphs with discrete vertex and edge
labels, here we propose extensions to deal with soft matches (Section 6.2.4)
and a larger class of graphs whose labels are tuples of mixed discrete and
19

numerical types (Section 6.2.5). In Section 6.3 we finally introduce a variant
of NSPDK with viewpoints, which can handle the case of multiple predictions
within the same interpretation. Similar extensions could be devised for other
kinds of kernels but we do not discuss them in this paper.
6.2.1. Kernel definition and notation
The NSPDK is an instance of a decomposition kernel, where “parts” are
pairs of subgraphs (for more details on decomposition kernels see Appendix
C). For a given graph G = (V, E), and an integer r ≥ 0, let Nrv (G) denote
the subgraph of G rooted in v and induced by the set of vertices
Vrv = {x ∈ V : d? (x, v) ≤ r},

(2)

where d? (x, v) is the shortest-path distance between x and v 9 . A neighborhood is therefore a topological ball with center v. Let us also introduce the
following neighborhood-pair relation:
Rr,d = {(Nrv (G), Nru (G), G) : d? (u, v) = d}

(3)

that is, relation Rr,d identifies pairs of neighborhoods of radius r whose roots
are exactly at distance d. We define κr,d over graph pairs as the decomposition
kernel on the relation Rr,d , that is:
X
κr,d (G, G0 ) =
κ((A, B), (A0 , B 0 ))
(4)
−1
A, B ∈ Rr,d
(G)
−1
0
0
A , B ∈ Rr,d
(G0 )

−1
where Rr,d
(G) indicates the multiset of all pairs of neighborhoods of radius
r with roots at distance d that exist in G.
We can now obtain a flexible parametric family of kernel functions by
specializing the kernel κ. The general structure of κ is:

κ((A, B), (A0 , B 0 )) = κroot ((A, B), (A0 , B 0 ))κsubgraph ((A, B), (A0 , B 0 )).

(5)

In the following, we assume
κroot ((A, B), (A0 , B 0 )) = 1`(r(A))=`(r(A0 )) 1`(r(B))=`(r(B 0 ))
9

Conventionally d? (x, v) = ∞ if no path exists between x and v

20

(6)

where 1 denotes the indicator function, r(A) is the root of A and `(v) the label
of vertex v. The role of κroot is to ensure that only neighborhoods centered
on the same type of vertex will be compared. Assuming a valid kernel for
κsubgraph (in the following Sections we give details on concrete instantiations),
we can finally define the NSPDK as:
XX
K(G, G0 ) =
κr,d (G, G0 ).
(7)
r

d

For efficiency reasons we consider the zero-extension of K obtained by imposing an upper bound on the radius and the distance parameter: Kr∗ ,d∗ (G, G0 ) =
Pr∗ Pd∗
0
r=0
d=0 κr,d (G, G ), that is, we limit the sum of the κr,d kernels for all increasing values of the radius (distance) parameter up to a maximum given
value r∗ (d∗ ). Furthermore we consider a normalized version of κr,d , that
κr,d (G,G0 )
, to ensure that relations induced by all
is: κ̂r,d (G, G0 ) = √
0
0
κr,d (G,G)κr,d (G ,G )

values of radii and distances are equally weighted regardless of the size of the
induced part sets.
Finally, it is easy to show that the NSPDK is a valid kernel as: 1) it
is built as a decomposition kernel over the countable space of all pairs of
neighborhood subgraphs of graphs of finite size; 2) the kernel over parts is
a valid kernel; 3) the zero-extension to bounded values for the radius and
distance parameters preserves positive definiteness and symmetry; and 4) so
does the normalization step.
6.2.2. Subgraph kernels
The role of κsubgraph is to compare pairs of neighborhood graphs extracted
from two graphs. The application of the graphicalization procedure to diverse
relational datasets can potentially induce graphs with significantly different
characteristics. In some cases (discrete property domains) an exact matching
between neighborhood graphs is appropriate, in other cases however (continous properties domains) it is more appropriate to use a soft notion of
matching.
In the following sections, we introduce variants of κsubgraph to be used
when the atoms in the relational dataset can maximally have a single discrete
or continuous property, or when more general tuples of properties are allowed.
6.2.3. Exact graph matching
An important case is when the atoms, that are mapped by the graphicalization procedure to the vertex set of the resulting graph, can maximally
21

Figure 3: Illustration of NSPDK features. Top: pairs of neighborhood subgraphs at fixed
distance 6 for radii 0, 1, 2, and 3. Bottom: pairs of neighborhood subgraphs of fixed radius
1 at distances 0, 1, 2, and 3.

22

have a single discrete property. In this case, an atom r(c) becomes a vertex
v, whose label is obtained by concatenation of the signature name and the
attribute value. In this case, κsubgraph has the following form:
κsubgraph ((A, B), (A0 , B 0 )) = 1A∼
=A0 1B ∼
=B 0

(8)

where 1 denotes the indicator function and ∼
= isomorphism between graphs.
Note that 1A∼
=A0 is a valid kernel between graphs under the feature map φcl
that transforms A into φcl (A), a sequence of all zeros except the i-th element
equal to 1 in correspondence to the identifier for the canonical representation
of A [43, 44].
Evaluating the kernel in Equation 8 requires as a subroutine graph isomorphism, a problem for which it is unknown whether polynomial algorithms
exist. Algorithms that are in the worst case exponential but that are fast
in practice do exist [43, 44]. For special graph classes, such as bounded degree graphs [45], there exist polynomial time algorithms. However, since it is
hard to limit the type of graph produced by the graphicalization procedure
(e.g., cases with very high vertex degree are possible as in general an entity
atom may play a role in an arbitrary number of relationship atoms), we prefer an approximate solution with efficiency guarantees based on topological
distances similar in spirit to [46].
The key idea is to compute an integer pseudo-identifier for each graph such
that isomorphic graphs are guaranteed to bear the same number (i.e., the
function is a graph invariant), but non-isomorphic graphs are likely to bear a
different number. A trivial identity test between the pseudo-identifiers then
approximates the isomorphism test. Appendix D details the computation
of the pseudo-identifier.
6.2.4. Soft matches
The idea of counting exact neighborhood subgraphs matches to express
graph similarity is adequate when the graphs are sparse (that is, when the
edge and the vertex set sizes are of the same order) and when the maximum vertex degree is low. However, when the graph is not sparse or some
vertices exhibit large degrees, the likelihood that two neighborhoods match
exactly quickly approaches zero, yielding a diagonal dominant kernel prone
to overfitting10 . In these cases a better solution is to relax the all-or-nothing
10

A concrete example is when text information associated to a document is modeled
explicitly, i.e., when word entities are linked to a document entity: in this case the degree

23

type of match, allowing subgraphs to match partially or in a soft way. Although there exist several graph kernels that are based on this type of match,
they generally suffer from very high computational costs [41]. To ensure efficiency, we use an idea introduced in the Weighted Decomposition Kernel
[47]: given a subgraph, we consider only the multinomial distribution (i.e.,
the histogram) of the labels, discarding all structural information. In the soft
match kernel, the comparison between two pairs of neighborhood subgraphs
is replaced by11 :
X
κsubgraph ((A, B), (A0 , B 0 )) =
1`(v)=`(v0 )
(9)
v ∈ V (A) ∪ V (B)
v 0 ∈ V (A0 ) ∪ V (B 0 )
where V (A) is the set of vertices of A. In words, for each pair of close
neighborhoods, we build a histogram counting the vertices with the same
label in either of the neighborhood subgraphs. The kernel is then computed
as the dot product of the corresponding histograms.
6.2.5. Tuples of properties
A standard assumption in graph kernels is that vertex and edge labels are
elements of a discrete domain. However, in kLog the information associated
with vertices is a tuple that can contain both discrete and real values. Here
we extend NSPDK to allow both a hard and a soft match type over graphs
with property tuples that can be discrete, real, or a mix of both types. While
similar extensions can be conceived, in principle, for other graph kernels, the
literature has mainly focused on kernels with single categorical labels. The
key idea is to use the canonical vertex identifier (introduced in Section 6.2.3)
to further characterize each property: in this way the kernel is defined only
between tuples of vertices that correspond under isomorphism.
The general structure of the kernel on the subgraph can be written as:
X
κsubgraph ((A, B), (A0 , B 0 )) =
1`(v)=`(v0 ) κtuple (v, v 0 )
(10)
v ∈ V (A) ∪ V (B)
v 0 ∈ V (A0 ) ∪ V (B 0 )

corresponds to the document vocabulary size.
11
Note that the pair of neighborhood subgraphs are considered jointly, i.e., the label
multisets are extracted independently from each subgraph in the pair and then combined
together.

24

C

A

C

A
A

A

B
C

C

A
A

A

C

A
A

C
B

C

A

+

A

C
B

C

=

A

B

C

A

B

C

C
A

C

A

x =

C

C

B
C

C

C
C
A

B

C

C

+

A

B

C

=

A

B C

A

B

A

A

A

A

C

C

C

C

A

A

C

C

C

C

A

A

B B

C

C

C

C

A

A

B B

C

C

C

C

5x2+2x2+4x4 = 30

C

Figure 4: Illustration of the soft matching kernel. Only features generated by a selected
pair of vertices are represented: vertices A and B at distance 1 yield a multinomial distribution of the vertex labels in neighborhoods of radius 1. On the right we compute the
contribution to the kernel value by the represented features.

where, for an atom12 r(c1 , c2 , . . . , cm ) mapped into vertex v, `(v) returns the
signature name r. κsubgraph is a kernel that is defined over sets of vertices
(atoms) and can be decomposed in a part that ensures matches between
atoms with the same signature name, and a second part that takes into
account the tuple of property values. In particular, depending on the type of
property values and the type of matching required, we obtain the following
six cases.
Soft match for discrete tuples. When the tuples contain only discrete
elements and one chooses to ignore the structure in the neighborhood graphs,
then each property is treated independently. Formally:
X
κtuple (v, v 0 ) =
1propd (v)=propd (v0 )
(11)
d

where for an atom r(c1 , c2 , . . . , cd , . . . , cm ) mapped into vertex v, propd (v)
12

We remind the reader that in the graphicalization procedure we remove the primary
and foreign keys from each atom, hence the only information available at the graph level
are the signature name and the properties values.

25

returns the property value cd .
Hard match for discrete tuples. When the tuples contain only discrete
elements and one chooses to consider the structure, then each property key
is encoded taking into account the identity of the vertex in the neighborhood
graph and all properties are required to match jointly. In practice, this
is equivalent to the hard match of Section 6.2.3 where the property value is
replaced with the concatenation of all property values in the tuple. Formally,
we replace the label `(v) in Equation 10 with the labeling procedure Lv
explained in Section 6.2.3. In this way, each vertex receives a canonical
label that uniquely identifies it in the neighborhood graphs. The double
summation of 1`(v)=`(v0 ) in Eq. 10 is then performing the selection of the
corresponding vertices v and v 0 in the two pairs of neighborhood that are
being compared. Finally, we consider all the elements of the tuple jointly in
order to identify a successful match:
Y
κtuple (v, v 0 ) =
1propd (v)=propd (v0 ) .
(12)
d

Soft match for real tuples. To upgrade the soft match kernel to tuples
of real values we replace the exact match with the standard product13 . The
kernel on the tuple then becomes:
X
κtuple (v, v 0 ) =
propc (v) · propc (v 0 ).
(13)
c

Hard match for real tuples. We proceed in an analogous fashion as
for the hard match for discrete tuples, that is, we replace the label `(v)
in Equation 10 with the labeling procedure Lv . In this case, however, we
combine the real valued tuple of corresponding vertices with the standard
product as in Equation 13:
X
κtuple (v, v 0 ) =
propc (v) · propc (v 0 ).
(14)
c

Soft match for mixed discrete and real tuples. When dealing with
tuples of mixed discrete and real values, the contribution of the kernels on
13

Note that this is equivalent to collecting all numerical properties of a vertex’s tuple in
a vector and then employ the standard dot product between vectors.

26

the separate collections of discrete and real attributes are combined via summation:
X
X
κtuple (v, v 0 ) =
1propd (v)=propd (v0 ) +
propc (v) · propc (v 0 )
(15)
c

d

where indices d and c run exclusively over the discrete and continous properties respectively.
Hard match for mixed discrete and real tuples. In an analogous fashion, provided that `(v) in Equation 10 is replaced with the labeling procedure
Lv (see Section 6.2.3) we have:
Y
X
propc (v) · propc (v 0 ).
(16)
κtuple (v, v 0 ) =
1propd (v)=propd (v0 ) +
c

d

In this way, each vertex receives a canonical label that uniquely identifies it
in the neighborhood graph. The discrete labels of corresponding vertices are
concatenated and matched for identity, while the real tuples of corresponding
vertices are combined via the standard dot product.
6.2.6. Domain knowledge bias via kernel points
At times it is convenient, for efficiency reasons or to inject domain knowledge into the kernel, to be able to explicitly select the neighborhood subgraphs. We provide a way to do so, declaratively, by introducing the set of
kernel points, a subset of V (G) which includes all vertices associated with
ground atoms of some specially marked signatures. We then redefine the
relation Rr,d (A, B, G) used in Equation 4 like in Section 6.2.1 but with the
additional constraints that the roots of A and B be kernel points.
Kernel points are typically vertices that are believed to represent information of high importance for the task at hand. Vertices that are not kernel
points contribute to the kernel computation only when they occur in the
neighborhoods of kernel points. In kLog, kernel points are declared as a list
of domain relations: all vertices that correspond to ground atoms of these
relations become kernel points.
6.3. Viewpoints
The above approach effectively defines a kernel over interpretations
K(z, z 0 ) = K(Gz , Gz0 )
27

in_phase(post_generals)
>209<

*on_same_paper
>81<

c

years_in_program(year_5)
>256<

has_position(faculty)
*on_same_paper
>132<
>69<

advised_by
>164<

*student
person21
>52<

*on_same_course
>126<

Wc
*on_same_paper
>80<

has_position(faculty)
>142<

*on_same_500_course
>108<

*on_same_paper
>89<
*professor
person211
>15<

*student
person45
>47<

in_phase(post_quals)
>224<

*on_same_paper
>103<
*professor
person407
>24<

advised_by
>160<

*on_same_paper
>104<
*on_same_paper
>87<
*on_same_paper
>102<

*student
person284
>1<

years_in_program(year_3)
>271<

advised_by
>145<

*on_same_paper
>100<

*student
person14
>3<

advised_by
>158<
advised_by
>170<
advised_by
>154<

in_phase(post_generals)
>197<

years_in_program(year_10)
>244<
*on_same_paper
>101<

Figure 5: A sample viewpoint (Wc ) in the UW-CSE domain, and the corresponding
mutilated graph where removed vertices are grayed out and the target case c highlighted.

where Gz is the result of graphicalization applied to interpretation z. For
learning jobs such as classification or regression on interpretations (see Table 2), this kernel is directly usable in conjunction with plain kernel machines like SVM. When moving to more complex jobs involving, e.g., classification of entities or tuples of entities, the kernel induces a feature vector
φ(x, y) suitable for the application of a structured output technique where
f (x) = arg maxy w> φ(x, y). Alternatively, we may convert the structured
output problem into a set of independent subproblems as follows. For simplicity, assume the learning job consists of a single relation r of relational
arity n. We call each ground atom of r a case. Intuitively, cases correspond
to training targets or prediction-time queries in supervised learning. Usually
an interpretation contains several cases corresponding to specific entities such
as individual Web pages (as in Section 5.3) or movies (as in Section 5.4), or
tuples of entities for link prediction problems (as in Section 2). Given a case
c ∈ y, the viewpoint of c, Wc , is the set of vertices that are adjacent to c
in the graph. In order to define the kernel, we first consider the mutilated
graph Gc where all vertices in y, except c, are removed (see Figure 5 for an
illustration). We then define a kernel κ̂ on mutilated graphs, following the
same approach of the NSPDK, but with the additional constraint that the
first endpoint must be in Wc . The decomposition is thus defined as
R̂r,d = {(A, B, Gc ) : Nrv , Nru , v ∈ Wc , d? (u, v) = d}.
28

We obtain in this way a kernel “centered” around case c:
X
X
K̂(Gc , G0c0 ) =
δ(A, A0 )δ(B, B 0 )
r,d

−1
A, B ∈ R̂r,d
(Gc )
−1
0
0
A , B ∈ R̂r,d
(G0c0 )

and finally we let
K(G, G0 ) =

X

K̂(Gc , G0c0 ).

c∈y,c0 ∈y 0

This kernel corresponds to the potential
X
F (x, y) = w>
φ̂(x, c)
c

which is clearly maximized by maximizing, independently, all sub-potentials
w> φ̂(x, c) with respect to c.
By following this approach, we do not obtain a collective prediction (individual ground atoms are predicted independently). Still, even in this reduced
setting, the kLog framework can be exploited in conjunction with metalearning approaches that surrogate collective prediction. For example, Prolog predicates in intensional signatures can effectively be used as expressive
relational templates for stacked graphical models [48] where input features
for one instance are computed from predictions on other related instances.
Results in Section 7.2 for the “partial information” setting are obtained using
a special form of stacking.
6.4. Parameterization in kLog
The kernels presented in this section, together with the graphicalization procedure, yield a statistical model working in a potentially very highdimensional feature space. Although large-margin learners offer some robustness against high-dimensional representations, it is still the user’s responsibility to choose appropriate kernel parameters (r∗ and d∗ ) to avoid overfitting.
It should be noted that subgraphs in the NSPDK effectively act like templates which are matched against graphicalized interpretations for new data.
Since identifiers themselves do not appear in the result of the graphicalization procedure, the same template can match multiple times realizing a form
of parameter tying as in other statistical relational learning methods.

29

7. kLog in practice
In this section, we illustrate the use of kLog in a number of application
domains. All experimental results reported in this section were obtained
using LibSVM in binary classification, multiclass, or regression mode, as
appropriate.
7.1. Predicting a single property of one interpretation
We now expand the ideas outlined in Example 5.1. Predicting the biological activity of small molecules is a major task in chemoinformatics
and can help drug development [49] and toxicology [50, 51]. Most existing graph kernels have been tested on data sets of small molecules (see,
e.g., [37, 38, 39, 41, 52]). From the kLog perspective the data consists of several interpretations, one for each molecule. In the case of binary classification
(e.g., active vs. nonactive), there is a single target predicate whose truth state
corresponds to the class of the molecule. To evaluate kLog we used two data
sets. The Bursi data set [53] consists of 4,337 molecular structures with
associated mutagenicity labels (2,401 mutagens and 1,936 nonmutagens) obtained from a short-term in vitro assay that detects genetic damage. The
Biodegradability data set [54] contains 328 compounds and the regression
task is to predict their half-life for aerobic aqueous biodegradation starting
from molecular structure and global molecular measurements.
Listing 4 shows a kLog script for the Bursi domain. Relevant predicates
in the extensional database are a/2, b/3 (atoms and bonds, respectively, extracted from the chemical structure), sub/3 (functional groups, computed
by DMax Chemistry Assistant [55, 56]), fused/3, connected/4 (direct connection between two functional groups), linked/4 (connection between functional groups via an aliphatic chain). Aromaticity (used in the bond-type
property of b/3) was also computed by DMax Chemistry Assistant. The
intensional signatures essentially serve the purpose of simplifying the original data representation. For example atm/2 omits some entities (hydrogen
atoms), and fg_fused/3 replaces a list of atoms by its length. In signature bnd(atom_1@b::atm,atom_2@b::atm) we use a role field b (introduced
by the symbol @). Using the same role twice declares that the two atoms
play the same role in the chemical bond, i.e. that the relation is symmetric.
In this way, each bond can be represented by one tuple only, while a more
traditional relational representation, which is directional, would require two
tuples. While this may at first sight appear to be only syntactic sugar, it
30

Table 3: Results (AUROC, 10-fold cross-validation) on the Bursi data set with and
without functional groups. The following kernel and SVM hyperparameters are varied:
maximum radius r∗ , maximum distance d∗ , and regularization parameter C.

C

d∗
8

0.5 10
12

8
1.0 10
12

8
2.0 10
12

8
5.0 10
12

r∗
4
6
8
4
6
8
4
6
8
4
6
8
4
6
8
4
6
8
4
6
8
4
6
8
4
6
8
4
6
8
4
6
8
4
6
8

With functional groups
0.90 ± 0.01
0.90 ± 0.02
0.89 ± 0.01
0.90 ± 0.02
0.90 ± 0.01
0.89 ± 0.02
0.90 ± 0.01
0.90 ± 0.01
0.89 ± 0.02
0.91 ± 0.01
0.91 ± 0.02
0.90 ± 0.01
0.91 ± 0.02
0.91 ± 0.02
0.90 ± 0.02
0.91 ± 0.01
0.91 ± 0.02
0.90 ± 0.01
0.91 ± 0.01
0.91 ± 0.02
0.90 ± 0.01
0.92 ± 0.01
0.91 ± 0.01
0.90 ± 0.01
0.91 ± 0.01
0.91 ± 0.01
0.90 ± 0.01
0.91 ± 0.01
0.91 ± 0.02
0.91 ± 0.02
0.91 ± 0.01
0.91 ± 0.01
0.90 ± 0.01
0.91 ± 0.02
0.91 ± 0.02
0.90 ± 0.01
31

Atom bond
0.88 ± 0.01
0.88 ± 0.02
0.88 ± 0.01
0.88 ± 0.02
0.88 ± 0.01
0.88 ± 0.02
0.88 ± 0.01
0.88 ± 0.01
0.88 ± 0.02
0.89 ± 0.01
0.89 ± 0.02
0.89 ± 0.01
0.89 ± 0.02
0.89 ± 0.02
0.89 ± 0.02
0.89 ± 0.01
0.89 ± 0.02
0.89 ± 0.01
0.90 ± 0.01
0.90 ± 0.02
0.89 ± 0.01
0.90 ± 0.01
0.90 ± 0.01
0.89 ± 0.01
0.89 ± 0.01
0.90 ± 0.01
0.89 ± 0.01
0.90 ± 0.01
0.90 ± 0.02
0.89 ± 0.02
0.90 ± 0.01
0.90 ± 0.01
0.89 ± 0.01
0.90 ± 0.02
0.90 ± 0.02
0.89 ± 0.01

1
2
3

4
5
6
7

8
9

10
11

12
13

14
15
16
17

18
19
20
21
22

23
24

begin_domain.
signature atm(atom_id::self , element::property )::intensional.
atm(Atom, Element) :- a(Atom,Element), \+(Element=h).
signature bnd(atom_1@b::atm, atom_2@b::atm, type::property )::intensional.
bnd(Atom1,Atom2,Type) :b(Atom1,Atom2,NType), describeBondType(NType,Type),
atm(Atom1,_), atm(Atom2,_).
signature fgroup(fgroup_id::self , group_type::property )::intensional.
fgroup(Fg,Type) :- sub(Fg,Type,_).
signature fgmember(fg::fgroup, atom::atm)::intensional.
fgmember(Fg,Atom):- subat(Fg,Atom,_), atm(Atom,_).
signature fg_fused(fg1@nil::fgroup, fg2@nil::fgroup, nrAtoms::property )::intensional.
fg_fused(Fg1,Fg2,NrAtoms):- fused(Fg1,Fg2,AtomList), length(AtomList,NrAtoms).
signature fg_connected(fg1@nil::fgroup, fg2@nil::fgroup,
bondType::property )::intensional.
fg_connected(Fg1,Fg2,BondType):connected(Fg1,Fg2,Type,_AtomList),describeBondType(Type,BondType).
signature fg_linked(fg::fgroup, alichain::fgroup, saturation::property )::intensional.
fg_linked(FG,AliChain,Sat) :linked(AliChain,Links,_BranchesEnds,Saturation),
( Saturation = saturated -> Sat = saturated ; Sat = unsaturated ),
member(link(FG,_A1,_A2),Links).
signature mutagenic::extensional.
end_domain.

Listing 4: Complete specification of the Bursi domain.

32

Table 4: Tilde results on Bursi.

Setting
Model
Functional groups Tilde
Functional groups Bagging 20x Tilde
Atom bonds
Tilde
Atom bonds
Bagging 20x Tilde

AUC
0.63 ±
0.79 ±
0.80 ±
0.83 ±

0.09
0.06
0.02
0.02

does provide extra abilities for modeling which is important in some domains.
For instance, when modeling ring-structures in molecules, traditional logical
and relational learning systems need to employ either lists to capture all the
elements in a ring structure, or else need to include all permutations of the
atoms participating in a ring structure. For rings involving 6 atoms, this requires 6!=720 different tuples, an unnecessary blow-up. Also, working with
lists typically leads to complications such as having to deal with a potentially
infinite number of terms. The target relation mutagenic has relational arity
zero since it is a property of the whole interpretation.
As shown in Table 3, results are relatively stable with respect to the
choice of kernel hyperparameter (maximum radius and distance) and SVM
regularization and essentially match the best results reported in [11] (AUROC
0.92±0.02) even without composition with a polynomial kernel. These results
are not surprising since the graphs generated by kLog are very similar in this
case to the expanded molecular graphs used in [11].
We compared kLog to Tilde on the same task. A kLog domain specification can be trivially ported to background knowledge for Tilde. Both systems
can then access the same set of Prolog atoms. Table 4 summarizes the results
and can be compared with Table 3. Augmenting the language with the functional groups from [56] unexpectedly gave worse results in Tilde compared
to a plain atom-bond language. The presence of some functional groups
correlates well with the target and hence those tests are used near the root
of the decision tree. Unfortunately, the greedy learner is unable to refine
its hypothesis down to the atom level and relies almost exclusively on the
coarse-grained functional groups. Such local-optimum traps can sometimes
be escaped from by looking ahead further, but this is expensive and Tilde
ran out of memory for lookaheads higher than 1. Tilde’s built-in bagging can
boost its results, especially when functional groups are used. A comparison
between Tables 4 and 3 shows that Tilde with our language bias definition
is not well suited for this problem.
33

Table 5: kLog results on biodegradability.

Setting
RMSE
SCC
MAPE
Functional groups 1.07 ± 0.01 0.54 ± 0.01 14.01 ± 0.08
Atom bonds
1.13 ± 0.01 0.48 ± 0.01 14.55 ± 0.12
The kLog code for biodegradability is similar to Bursi but being a regression task we have a target relation declared as
signature biodegradation(halflife::property )::extensional.
We estimated prediction performance by repeating five times a ten-fold cross
validation procedure as described in [54] (using exactly the same folds in
each trial). Results — rooted mean squared error (RMSE), squared correlation coefficient (SCC), and mean absolute percentage error (MAPE) — are
reported in Table 5. For comparison, the best RMSE obtained by kFOIL on
this data set (and same folds) is 1.14 ± 0.04 (kFOIL was shown to outperform
Tilde and S-CART in [5]).
7.2. Link prediction
We report here experimental results on the UW-CSE domain that we
have already extensively described in Section 2. To assess kLog behavior we
evaluated prediction accuracy according to the leave-one-research-group-out
setup of [7], using the domain description of Listings 2 and 3, together with
a NSPDK kernel with distance 2, radius 2, and soft match. Comparative
results with respect to Markov logic are reported in Figure 6 (MLN results
published in [7]). The whole 5-fold procedure runs in about 20 seconds on a
single core of a 2.5GHz Core i7 CPU. Compared to MLNs, kLog in the current
implementation has the disadvantage of not performing collective assignment
but the advantage of defining more powerful features thanks to the graph
kernel. Additionally, MLN results use a much larger knowledge base. The
advantage of kLog over MLN in Figure 6 is due to the more powerful feature
space. Indeed, when setting the graph kernel distance and radius to 0 and 1,
respectively, the feature space has just one feature for each ground signature,
in close analogy to MLN. The empirical performance (area under recallprecision curve, AURPC) of kLog using the same set of signatures drops
dramatically from 0.28 (distance 2, radius 2) to 0.09 (distance 1, radius 0).
In a second experiment, we predicted the relation advised_by starting
from partial information (i.e., when relations Student (and its complement
34

Professor) are unknown, as in [7]). In this case, we created a pipeline of two
predictors. Our procedure is reminiscent of stacked generalization [57]. In
the first stage, a leave-one-research-group-out cross-validation procedure was
applied to the training data to obtain predicted groundings for Student (a
binary classification task on entities). Predicted groundings were then fed to
the second stage which predicts the binary relation advised_by. The overall
procedure was repeated using one research group at the time for testing.
Results are reported in Figure 7 (MLN results published in [7]).
Since kLog is embedded in the programming language Prolog, it is easy
to use the output of one learning task as the input for the next one as
illustrated in the pipeline. This is because both the inputs and the outputs
are relations. Relations are treated uniformly regardless of whether they are
defined intensionally, extensionally, or are the result of a previous learning
run. Thus kLog satisfies what has been called the closure principle in the
context of inductive databases [58, 59]; it is also this principle together with
the embedding of kLog inside a programming language (Prolog) that turns
kLog into a true programming language for machine learning [60, 61, 62].
Such programming languages possess — in addition to the usual constructs
— also primitives for learning, that is, to specify the inputs and the outputs of
the learning problems. In this way, they support the development of software
in which machine learning is embedded without requiring the developer to
be a machine learning expert. According to Mitchell [60], the development
of such languages is a long outstanding research question.
7.3. Entity classification
The WebKB data set [27] has been widely used to evaluate relational
methods for text categorization. It consists of academic Web pages from
four computer science departments and the task is to identify the category
(such as student page, course page, professor page, etc). Figure 8 shows
the E/R diagram used in kLog. One of the most important relationships in
this domain is has, that associates words to web pages. After graphicalization, vertices representing webpages have large degree (at least the number
of words), making the standard NSPDK of [11] totally inadequate: even by
setting the maximum distance d∗ = 1 and the maximum radius r∗ = 2, the
hard match would essentially create a distinct feature for every page. In this
domain we can therefore appreciate the flexibility of the kernel defined in Section 6.2. In particular, the soft match kernel creates histograms of word occurrences in the page, which is very similar to the bag-of-words (with counts)
35

0.6
0.5
0.4
0.3
0.2
0.1
1.0 0.00.0

MLN
kLog

0.2

0.4 0.6
Recall

0.8

MLN
kLog

1.0
0.8
0.6
0.4
0.2
0.00.0

0.2

0.4 0.6
Recall

0.8

MLN
kLog

0.2

0.4 0.6
Recall

0.8

1.0

theory (all)
MLN
kLog

Precision

Precision

1.0
0.8
0.6
0.4
0.2
0.00.0

1.0

graphics (all)

Precision

languages (all)
0.7
0.6
MLN
0.5
kLog
0.4
0.3
0.2
0.1
0.00.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Recall
systems
(all)
1.0
MLN
0.8
kLog
0.6
0.4
0.2
0.00.0 0.2 0.4 0.6 0.8 1.0
Recall

Precision

ai (all)

Precision

All (all)

Precision

0.6
0.5
0.4
0.3
0.2
0.1
0.00.0

0.2

0.4 0.6
Recall

0.8

1.0

Figure 6: Comparison between kLog and MLN on the UW-CSE domain (all information).

0.6
0.5
0.4
0.3
0.2
0.1
1.0 0.00.0

MLN
kLog

0.2

0.4 0.6
Recall

0.8

MLN
kLog

0.4 0.6
Recall

0.8

1.0
0.8
0.6
0.4
0.2
0.00.0

1.0

graphics (partial)
MLN
kLog

Precision

1.0
0.8
0.6
0.4
0.2
0.00.0

0.2

0.2

0.4 0.6
Recall

0.8

1.0

theory (partial)
MLN
kLog

Precision

Precision

Precision

languages (partial)
1.0
MLN
0.8
kLog
0.6
0.4
0.2
0.00.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Recall
systems
(partial)
1.0
MLN
0.8
kLog
0.6
0.4
0.2
0.00.0 0.2 0.4 0.6 0.8 1.0
Recall

Figure 7:
mation).

ai (partial)

Precision

All (partial)

Precision

0.6
0.5
0.4
0.3
0.2
0.1
0.00.0

0.2

0.4 0.6
Recall

0.8

1.0

Comparison between kLog and MLN on the UW-CSE domain (partial infor-

36

cat

category
url

has
page

word
cs_in_url
target

source
link_to

has_anchor

link

word

link-id

Figure 8: WebKB domain.

representation that is commonly used in text categorization problems. The
additional signature cs_in_url embodies common sense background knowledge that many course web pages contains the string “cs” followed by some
digits and is intensionally defined using a Prolog predicate that holds true
when the regular expression :cs(e*)[0-9]+: matches the page URL.
Empirical results using only four Universities (Cornell, Texas, Washington, Wisconsin) in the leave-one-university-out setup are reported in Table 6.
We compared kLog to MLN and to Tilde on the same task. For MLN we
used the Alchemy system and the following set of formulae, which essentially
encode the same domain knowledge exploited in kLog:
1
2
3
4
5
6

Has(+w,p) => Topic(+t,p)
!Has(+w,p) => Topic(+t,p)
CsInUrl(p) => Topic(+t,p)
!CsInUrl(p) => Topic(+t,p)
Topic(+c1, p1) ^ (Exist a LinkTo(a, p1, p2)) => Topic(+c2, p2)
HasAnchor(+w,a) ^ LinkTo(a, p1, p2) => Topic(+c, p2)

Ground atoms for the predicate LinkTo were actually precalculated externally
in Prolog (same code as for the kLog’s intensional signature) since regular
expressions are not available in Alchemy. We did not enforce mutually exclusive categories since results tended to be worse. For learning we used the
preconditioned scaled conjugate gradient approach described in [63] and we
37

Table 6: Results on WebKB (kLog): contingency table, accuracy, precision, recall, and F1
measure per class. Last row reports micro-averages.

research faculty course
research
59
11
4
faculty
9
125
2
course
0
0
233
student
16
17
5
Average

student
15
50
0
493

A
0.94
0.91
0.99
0.90
0.88

P
0.66
0.67
1.00
0.93
0.89

R
0.70
0.82
0.95
0.88
0.88

F1
0.68
0.74
0.98
0.91
0.88

Table 7: Results on WebKB (Markov logic): contingency table, accuracy, precision, recall,
and F1 measure per class. Last row reports micro-averages.

research faculty
research
42
3
faculty
1
91
course
0
1
student
1
9
Average

course student
A
P
7
32 0.95 0.95
1
60 0.92 0.88
233
10 0.98 0.95
3
545 0.89 0.84
0.88 0.91

R
0.50
0.59
0.95
0.98
0.76

F1
0.66
0.71
0.95
0.90
0.81

Table 8: Results on WebKB (Tilde): contingency table, accuracy, precision, recall, and F1
measure per class. Last row reports micro-averages.

research
faculty
course
student
Average

research faculty
39
9
11
110
1
1
9
39

course student
A
1
35 0.93
1
31 0.91
235
7 0.99
1
509 0.88
0.86

38

P
0.65
0.69
0.99
0.87
0.80

R F_1
0.46 0.54
0.72 0.71
0.96 0.98
0.91 0.89
0.76 0.78

tried a wide range of values for the learning rate and the number of iterations. The best results, reported in Table 6, used the trick of averaging MLN
weights across all iterations as in [63]. MC-SAT inference was used during
prediction. In spite of the advantage of MLN for using a collective inference approach, results are comparable to those obtained with kLog (MLN
tends to overpredict the class “student”, resulting in a slightly lower average
F1 measure, but accuracies are identical). Thus the feature extracted by
kLog using the graph kernel are capable of capturing enough contextual information from the input portion of the data to obviate the lack of collective
inference.
In the case of Tilde, we used the following language bias:
1
2
3

rmode((has(+U,Word,+Page), Word = #Word)).
rmode((cs_in_url(+U,+Page,V), V = #V)).
rmode((link_to(+U,-Link,-From,+Page), has_anchor(+U,Word,Link), Word = #Word)).

Results are reported in Table 8 and are slightly worse than those attained
by kLog and MLN.
Although the accuracies of the three methods are essentially comparable,
their requirements in terms of CPU time are dramatically different: using
a single core of a second generation Intel Core i7, kLog took 36s, Alchemy
27,041s (for 100 iterations, at which the best accuracy is attained), and Tilde:
5,259s.
7.4. Domains with a single interpretation
The Internet Movie Database (IMDb) collects information about movies
and their cast, people, and companies working in the motion picture industry.
We focus on predicting, for each movie, whether its first weekend box-office
receipts are over US$2 million, a learning task previously defined in [30, 64].
The learning setting defined so far (learning from independent interpretations) is not directly applicable since train and test data must necessarily
occur within the same interpretation. The notion of slicing in kLog allows
us to overcome this difficulty. A slice system is a partition of the true ground
atoms in a given interpretation: z = {z(i1 ), . . . , z(in )} where the disjoint sets
z(j) are called slices and the index set I = {i1 , . . . , in } is endowed with a
total order . For example, a natural choice for I in the IMDb domain is
the set of movie production years (e.g., {1996, . . . , 2005}), where the index
associated with a ground atom of an entity such as actor is the debut year.
39

In this way, given two disjoint subsets of I, T and S, such that max (T ) 
min (S), it is reasonable during training to use for some index t ∈ T \
{min (T )} the set of ground atoms {x(i) : i ∈ T ∧ i  t}t ∪ {y(i) : i ∈
T ∧ i ≺ t}t (where i ≺ t iff i  t and i 6= t) as the input portion of the data,
and {y(t)}t as the output portion (targets). Similarly, during testing we can
for each s ∈ S use the set of ground atoms {x(i) : i ∈ S ∧ i  s}s ∪ {y(i) :
i ∈ S ∧ i ≺ s}s for predicting {y(s)}s .
The kLog data set was created after downloading the whole database from
http://www.imdb.com. Adult movies, movies produced outside the US, and
movies with no opening weekend data were discarded. Persons and companies with a single appearance in this subset of movies were also discarded.
The resulting data set is summarized in Table 9. We modeled the domain
in kLog using extensional signatures for movies, persons (actors, producers,
directors), and companies (distributors, production companies, special effects companies). We additionally included intensional signatures counting,
for each movie the number of companies involved also in other blockbuster
movies. We sliced the data set according to production year, and starting
from year y = 1997, we trained on the frame {y − 1, y − 2} and tested on the
frame {y}. Results (area under the ROC curve) are summarized in Table 9,
together with comparative results against MLN and Tilde. In all three cases
we used the same set of ground atoms for training and testing, but in the case
of MLN the Alchemy software does not differentiate between evidence and
query ground atoms of the same predicate. We therefore introduced an extra
predicate called PrevBlockbuster to inject evidence for years {y −3, y−4, . . . },
together with the hard rule
1

PrevBlockbuster(m) <=> Blockbuster(m).

and used Blockbuster as the query predicate when training on years {y −
1, y − 2} and testing on year y. MLN rules were designed to capture past
performance of actors, directors, distribution companies, etc. For example:
1

ActedIn(p,m1) ^ ActedIn(p,m2) ^ Blockbuster(m1) ^ m1 != m2 => Blockbuster(m2)

In the case of Tilde, we used as background knowledge exactly the same intensional signature definitions used in kLog. The MLN was trained using the
discriminative weight learning algorithm implemented in Alchemy. MCMC
(Gibbs sampling) was used during prediction to obtain probabilities for all
query atoms.
40

Table 9: Results (AUC) on the IMDb data set. Years 1995 and 1996 were only used for
training. Years before 1995 (not shown) are always included in the training data.

Year # Movies # Facts
kLog
MLN
1995
74
2483
—
—
1996
223
6406
—
—
1997
311
8031
0.86
0.79
1998
332
7822
0.93
0.85
1999
348
7842
0.89
0.85
2000
381
8531
0.96
0.86
2001
363
8443
0.95
0.86
2002
370
8691
0.93
0.87
2003
343
7626
0.95
0.88
2004
371
8850
0.95
0.87
2005
388
9093
0.92
0.84
All
0.93 ± 0.03 0.85 ± 0.03

Tilde
—
—
0.80
0.88
0.85
0.93
0.91
0.89
0.87
0.87
0.83
0.87 ± 0.04

On this data set, Tilde was the fastest system, completing all training and
test phases in 220s, followed by kLog (1,394s) and Alchemy (12,812s). However, the AUC obtained by kLog is consistently higher across all prediction
years.
8. Related work
As kLog is a language for logical and relational learning with kernels it
is related to work on inductive logic programming, to statistical relational
learning, to graph kernels, and to propositionalization. We now discuss each
of these lines of work and their relation to kLog.
First, the underlying representation of the data that kLog employs at
the first level is very close to that of standard inductive logic programming
systems such as Progol [65], Aleph [66], and Tilde [67] in the sense that the
input is essentially (a variation of) a Prolog program for specifying the data
and the background knowledge. Prolog allows us to encode essentially any
program as background knowledge. The E/R model used in kLog is related to
the Probabilistic Entity Relationship models introduced by Heckerman et al.
in [10]. The signatures play a similar role as the notion of a declarative bias
in inductive logic programming [9]. The combined use of the E/R model and
the graphicalization has provided us with a powerful tool for visualizing both
the structure of the data (the E/R diagram) as well as specific cases (through
41

their graphs). This has proven to be very helpful when preparing datasets
for kLog. On the other hand, due to the adoption of a database framework,
kLog forbids functors in the signature relations (though functors can be used
inside predicates needed to compute these relations inside the background
knowledge). This contrasts with some inductive logic programming systems
such as Progol [65] and Aleph [66].
Second, kLog is related to many existing statistical relational learning
systems such as Markov logic [7], probabilistic similarity logic [68], probabilistic relational models [8], Bayesian logic programs [69], and ProbLog [70]
in that the representations of the inputs and outputs are essentially the same,
that is, both in kLog and in statistical relational learning systems inputs are
partial interpretations which are completed by predictions. What kLog and
statistical relational learning techniques have in common is that they both
construct (implicitly or explicitly) graphs representing the instances. For
statistical relational learning methods such as Markov logic [7], probabilistic
relational models [8], and Bayesian logic programs [69] the knowledge-based
model construction process will result in a graphical model (Bayesian or
Markov network) for each instance representing a class of probability distributions, while in kLog the process of graphicalization results in a graph
representing an instance by unrolling the E/R-diagram. Statistical relational
learning systems then learn a probability distribution using the features and
parameters in the graphical model, while kLog learns a function using the
features derived by the kernel from the graphs. Notice that in both cases, the
resulting features are tied together. Indeed, in statistical relational learning
each ground instance of a particular template or expression that occurs in the
graph has the same parameters. kLog features correspond to subgraphs that
represent relational templates and that may match (and hence be grounded)
multiple times in the graphicalization. As each such feature has a single
weight, kLog also realizes parameter tying in a similar way as statistical relational learning methods. One difference between these statistical relational
learning models and kLog is that the former do not really have a second
level as does kLog. Indeed, the knowledge base model construction process
directly generates the graphical model that includes all the features used
for learning, while in kLog these features are derived from the graph kernel.
While statistical relational learning systems have been commonly used for
collective learning, this is still a question for further research within kLog. A
combination of structured-output learning [12] and iterative approaches (as
incorporated in the EM algorithm) can form the basis for further work in
42

this direction. Another interesting but more speculative direction for future
work is concerned with lifted inference. Lifted inference has been the focus
of a lot of attention in statistical relational learning; see [71] for an overview.
One view on lifted inference is that it is trying to exploit symmetries in the
graphical models that would be the result of the knowledge based model
construction step, e.g., [72]. From this perspective, it might be interesting to
explore the use of symmetries in graphs and features constructed by kLog.
kLog builds also upon the many results on learning with graph kernels,
see [73] for an overview. A distinguishing feature of kLog is, however, that
the graphs obtained by graphicalizing a relational representation contain very
rich labels, which can be both symbolic and numeric. This contrasts with
the kind of graphs needed to represent for instance small molecules. In this
regard, kLog is close in spirit to the work of [74], who define a kernel on
hypergraphs, where hypergraphs are used to represent relational interpretations. A distinctive feature of kLog is automatic graphicalization of relational
representations, which also allows users to naturally specify multitask and
collective learning tasks.
The graphicalization approach introduced in kLog is closely related to
the notion of propositionalization, a commonly applied technique in logical
and relational learning [75, 9] to generate features from a relational representation. The advantage of graphicalization is that the obtained graphs are
essentially equivalent to the relational representation and that — in contrast
to the existing propositionalization approaches in logical and relational learning — this does not result in a loss of information. After graphicalization, any
graph kernel can in principle be applied to the resulting graphs. Even though
many of these kernels (such as the one used in kLog) compute — implicitly
or explicitly — a feature vector, the dimensionality of the obtained vector
is far beyond that employed by traditional propositionalization approaches.
kFOIL [5] is one such propositionalization technique that has been tightly
integrated with a kernel-based method. It greedily derives a (small) set of
features in a way that resembles the rule-learning algorithm of FOIL [76].
Several other approaches to relational learning and mining have employed
graph-based encodings of the relational data, e.g., [77, 78, 79, 80]. kLog encodes a set of ground atoms into a bipartite undirected graph whose nodes
are true ground atoms and whose edges connect an entity atom to a relationship atom if the identifier of the former appears as an argument in the latter.
This differs from the usual encoding employed in graph-based approaches to
relational learning and mining, which typically use labeled edges to directly
43

represent the relationships between the nodes corresponding to the entities.
Furthermore, these approaches typically use the graph-based representation
as the single representation, and unlike kLog do neither consider the graphbased representation as an intermediate representation nor work at three
levels of representation (logical, graph-based and feature-based).
Other domain specific languages for machine learning have been developed whose goals are closely related to those of kLog. Learning based
Java [62] was designed to specifically address applications in natural language processing. It builds on the concept of data-driven compilation to
perform feature extraction and nicely exploits the constrained conditional
model framework [81] for structured output learning. FACTORIE [82] allows
users to concisely define features used in a factor graph and, consequently,
arbitrarily connected conditional random fields. Like with MLN, there is an
immediate dependency of the feature space on the sentences of the language,
whereas in kLog this dependency is indirect since the exact feature space is
eventually defined by the graph kernel.
9. Conclusions
We have introduced a novel language for logical and relational learning
called kLog. It tightly integrates logical and relational learning with kernel methods and constitutes a principled framework for statistical relational
learning based on kernel methods rather than on graphical models. kLog
uses a representation that is based on E/R modeling, which is close to representations being used by contemporary statistical relational learners. kLog
first performs graphicalization, that is, it computes a set of labeled graphs
that are equivalent to the original representation, and then employs a graph
kernel to realize statistical learning. We have shown that the kLog framework can be used to formulate and address a wide range of learning tasks,
that it performs at least comparably to state-of-the-art statistical relational
learning techniques, and also that it can be used as a programming language
for machine learning.
The system presented in this paper is a first step towards a kernel-based
language for relational learning but there are unanswered questions and interesting open directions for further research. One important aspect is the
possibility of performing collective classification (or structured output prediction). Structured output learning problems can be naturally defined within
kLog’s semantics: graphicalization followed by a graph kernel yields a joint
44

feature vector φ(x, y) where y are the groundings of the output predicates.
Collective prediction amounts to maximizing w> φ(x, y) with respect to y.
There are two important cases to consider. If groundings in y do not affect
the graph structure (because they never affect the intensional signatures)
then the collective classification problem is not more complicated than in
related SRL systems. For example, if dependencies have a regular sequential
structure, dynamic programming can be used for this step, exactly as in conditional random fields (indeed, collective classification has been succesfully
exploited within kLog in an application to natural language test segmentation [83]). However, in general, changing y during search will also change
the graph structure. In principle it is feasible to redo graphicalization from
scratch during search, apply the graph kernel again and eventually evaluate
w> φ(x, y), but such a naive approach would of course be very inefficient. Developing clever and faster algorithms for this purpose is an interesting open
issue. It should be remarked, however, that even without collective classification, kLog achieves good empirical results thanks to the fact that features
produced by the graph kernel provide a wide relational context. Better understanding of generalization for structured prediction models has begun to
emerge (see [84] and references therein) and a theoretical analysis of learning within the present kLog setting is another potential direction for future
research.
The graph kernel that is currently employed in kLog makes use of the
notion of topological distances to define the concept of neighborhoods. In this
way, given a predicate of interest, properties of “nearby” tuples are combined
to generate features relevant for that predicate. As a consequence, when
topological distances are not informative (e.g., in the case of dense graphs
with small diameter) then large fractions of the graph become accessible
to any neighborhood and the features induced for a specific predicate cease
to be discriminative. In these cases (typical when dealing with small-world
networks), kernels with a different type of bias (e.g., flow-based kernels) are
more appropriate. The implementation of a library of kernels suitable for
different types of graphs, as well as the integration of other existing graph
kernels (such as [40, 41, 42]) in the kLog framework, is therefore an important
direction for future development.
Furthermore, even though kLog’s current implementation is quite performant, there are interesting implementation issues to be studied. Many of
these are similar to those employed in statistical relational learning systems
such as Alchemy [7] and ProbLog [85].
45

kLog is being actively used for developing applications. We are currently
exploring applications of kLog in natural language processing [86, 83, 87] and
in computer vision [88, 89, 90].
Acknowledgments
We thank Tom Schrijvers for his dependency analysis code. PF was supported partially by KU Leuven SF/09/014 and partially by Italian Ministry of
University and Research PRIN 2009LNP494. KDG was supported partially
by KU Leuven GOA/08/008 and partially by ERC Starting Grant 240186
“MiGraNT”. Finally, we would like to thank the anonymous reviewers and
the associate editor for their very useful and constructive comments.

46

Appendix A. Syntax of the kLog domain declaration section
A kLog program consists of Prolog code augmented by a domain declaration section delimited by the pair of keywords begin_domain and end_domain
and one or more signature declarations. A signature declaration consists of
a signature header followed by one or more Prolog clauses. Clauses in a
signature declaration form the declaration of signature predicates and are
automatically connected to the current signature header. There are a few
signature predicates with a special meaning for kLog, as discussed in this
section. A brief BNF description of the grammar of kLog domains is given
in Figure A.9.
Additionally, kLog provides a library of Prolog predicates for handling
data, learning, and performance measurement.
domain → begin_domain. signatures end_domain.
signatures → signature | [signature signatures]
signature → header [sig_clauses]
sig_clauses → sig_clause | [sig_clause sig_clauses]
sig_clause → Prolog_clause
header → signature sig_name ( args ) :: level .
sig_name → Prolog_atom
args → arg | [arg args]
arg → column_name [role_overrider] :: type
column_name → Prolog_atom
role_overrider → @ role
role → Prolog_atom
type → self | sig_name | property
level → intensional | extensional

Figure A.9: kLog syntax

Appendix B. Definitions
For the sake of completeness we report here a number of graph theoretical
definitions used in the paper. We closely follow the notation in [91]. A graph
G = (V, E) consists of two sets V and E. The notation V (G) and E(G) is
47

used when G is not the only graph considered. The elements of V are called
vertices and the elements of E are called edges. Each edge has a set of two
elements in V associated with it, which are called its endpoints, which we
denote by concatenating the vertices variables, e.g. we represent the edge
between the vertices u and v with uv. In this case we say that u is adjacent
to v and that uv is incident on u and v. The degree of a vertex is number of
edges incident on it. A graph is bipartite if its vertex set can be partitioned
into two subsets X and Y so that every edge has one end in X and the
other in Y . A graph is rooted when we distinguish one of its vertices, called
root. The neighborhood of a vertex v is the set of vertices that are adjacent
to v and is indicated with N (v). The neighborhood of radius r of a vertex
v is the set of vertices at a distance less than or equal to r from v and is
denoted by Nr (v). In a graph G, the induced subgraph on a set of vertices
W = {w1 , . . . , wk } is a graph that has W as its vertex set and it contains
every edge of G whose endpoints are in W . The neighborhood subgraph of
radius r of vertex v is the subgraph induced by the neighborhood of radius
r of v and is denoted by Nrv . A labeled graph is a graph whose vertices
and/or edges are labeled, possibly with repetitions, using symbols from a
finite alphabet. We denote the function that maps the vertex/edge to the
label symbol as `. Two simple graphs G1 = (V1 , E1 ) and G2 = (V2 , E2 ) are
isomorphic, which we denote by G1 ' G2 , if there is a bijection φ : V1 → V2 ,
such that for any two vertices u, v ∈ V1 , there is an edge uv if and only if
there is an edge φ(u)φ(v) in G2 . An isomorphism is a structure-preserving
bijection. Two labeled graphs are isomorphic if there is an isomorphism that
preserves also the label information, i.e. `(φ(v)) = `(v). An isomorphism
invariant or graph invariant is a graph property that is identical for two
isomorphic graphs (e.g. the number of vertices and/or edges). A certificate
for isomorphism is an isomorphism invariant that is identical for two graphs
if and only if they are isomorphic.
Appendix C. Decomposition kernels
We follow the notation in [92]. Given a set X and a function K : X ×X →
R, we say that K is a kernel on X × X if K is symmetric, i.e. if for any x
and y ∈ X K(x, y) = K(y, x), and if K is positive-semidefinite, i.e. if for any
N ≥ 1 and any x1 , . . . , xN ∈ X,Pthe matrix K defined by Kij = K(xi , xj )
is positive-semidefinite, that is
ij ci cj Kij ≥ 0 for all c1 , . . . , cN ∈ R or
equivalently if all its eigenvalues are nonnegative. It is easy to see that if
48

each x ∈ X can be represented as φ(x) = {φn (x)}P
n≥1 such that K is the
ordinary l2 dot product K(x, y) = hφ(x), φ(y)i =
n φn (x)φn (y) then K
is a kernel. The converse is also true under reasonable assumptions (which
are almost always verified) on X and K, that is, a given kernel K can be
represented as K(x, y) = hφ(x), φ(y)i for some choice of φ. In particular it
holds for any kernel K over X × X where X is a countable set. The vector
space induced by φ is called the feature space. Note that it follows from the
definition of positive-semidefinite that the zero-extension of a kernel is a valid
kernel, that is, if S ⊆ X and K is a kernel on S × S then K may be extended
to be a kernel on X × X by defining K(x, y) = 0 if x or y is not in S. It is
easy to show that kernels are closed under summation, i.e. a sum of kernels
is a valid kernel.
Let now x ∈ X be a composite structure such that we can define x1 , . . . , xD
as its parts14 . Each part is such that xd ∈ Xd for d = 1, . . . , D with D ≥ 1
where each Xd is a countable set. Let R be the relation defined on the set
X1 × . . . × XD × X, such that R(x1 , . . . , xD , x) is true iff x1 , . . . , xD are the
parts of x. We denote with R−1 (x) the inverse relation that yields the parts of
x, that is R−1 (x) = {x1 , . . . , xD : R(x1 , . . . , xD , x)}. In [92] it is demonstrated
that, if there exist a kernel Kd over Xd × Xd for each d = 1, . . . , D, and if
two instances x, y ∈ X can be decomposed in x1 , . . . , xd and y1 , . . . , yd , then
the following generalized convolution:
K(x, y) =

M
Y

X

Km (xm , ym )

(C.1)

R−1 (x)

m=1
x1 , . . . , xm ∈
y1 , . . . , ym ∈ R−1 (y)

is a valid kernel called a convolution or decomposition kernel15 . In words:
a decomposition kernel is a sum (over all possible ways to decompose a structured instance) of the product of valid kernels over the parts of the instance.
Appendix D. Graph invariant pseudo-identifier computation
We obtain the pseudo-identifier of a rooted neighborhood graph Gh by
first constructing a graph invariant encoding Lg (Gh ). Then we apply a hash
14

Note that the set of parts needs not be a partition for the composite structure, i.e.
the parts may “overlap”.
15
To be precise, the valid kernel is the zero-extension of K to X × X since R−1 (x) is
not guaranteed to yield a non-empty set for all x ∈ X.

49

root vertex

A

12

C

B

4

vertex label
hashing

B

4 12

23
56

4 56

12 23

23 56

sorted edge
representation

656712
hash

Example of vertex label hashing for C
A
B

1A

example vertex

C

2B

augment with
B pairwise distances 1B
from C to all vertices

1ROOT 0C 1A 1B 2B

0C

sorted vertex
representation

23
hash

Figure D.10: Graph invariant computation: the graph hash is computed as the hash of
the sorted list of edge hashes. An edge hash is computed as the hash of the sequence of
the two endpoints hashes and the edge label. The endpoint hash is computed as the hash
of the sorted list of distance-vertex label pairs.

function H(Lg (Gh )) → N to the encoding. The algorithm was first described
in [11] but we present it again here for self-sufficiency. Figure D.10 shows an
overview.
Note that we cannot hope to exhibit an efficient certificate for isomorphism in this way, and in general there can be collisions between two nonisomorphic graphs, either because these are assigned the same encoding or
because the hashing procedure introduces a collision even when the encodings
are different.
Hashing is not a novel idea in machine learning; it is commonly used,
e.g., for creating compact representations of molecular structures [38], and
has been advocated as a tool for compressing very high-dimensional feature
spaces [93]. In the present context, hashing is mainly motivated by the
computational efficiency gained by approximating the isomorphism test.
The graph encoding Lg (Gh ) that we propose is best described by introducing two new label functions: one for the vertices and one for the edges,
denoted Lv and Le respectively. Lv (v) assigns to vertex v a lexicographically
sorted sequence of pairs composed by a topological distance and a vertex label, that is, Lv (v) returns a sorted list of pairs hD(v, u), `(u)i for all u ∈ Gh .
Moreover, since Gh is a rooted graph, we can use the knowledge about the
identity of the root vertex h and prepend to the returned list the additional
50

information of the distance from the root node D(v, h). The new edge label
is produced by composing the new vertex labels with the original edge label,
that is Le (uv) assigns to edge uv the triplet hLv (u), Lv (v), `(uv)i. Finally
Lg (Gh ) assigns to the rooted graph Gh the lexicographically sorted list of
Le (uv) for all uv ∈ E(Gh ). In words: we relabel each vertex with a sequence
that encodes the vertex distance from all other (labeled) vertices (plus the
distance from the root vertex); the graph encoding is obtained as the sorted
edge list, where each edge is annotated with the endpoints’ new labels. For
a proof that Lg (Gh ) is graph invariant, see [94, p. 53].
We finally resort to a Merkle-Damgård construction-based hashing function for variable-length data to map the various lists to integers, that is, we
map the distance-label pairs, the new vertex labels, the new edge labels and
the new edge sequences to integers (in this order). Note that it is trivial to
control the size of the feature space by choosing the hash codomain size (or
alternatively the bit size for the returned hashed values). Naturally there
is a tradeoff between the size of the feature space and the number of hash
collisions.
References
[1] T. Dietterich, P. Domingos, L. Getoor, S. Muggleton, P. Tadepalli,
Structured machine learning: the next ten years, Mach Learn 73 (2008)
3–23.
[2] L. De Raedt, B. Demoen, D. Fierens, B. Gutmann, G. Janssens, A. Kimmig, N. Landwehr, T. Mantadelis, W. Meert, R. Rocha, et al., Towards
digesting the alphabet-soup of statistical relational learning (2008).
[3] L. De Raedt, P. Frasconi, K. Kersting, S. Muggleton (Eds.), Probabilistic inductive logic programming: theory and applications, Vol. 4911 of
Lecture notes in computer science, Springer, Berlin, 2008.
[4] L. Getoor, B. Taskar (Eds.), Introduction to statistical relational learning, MIT Press, Cambridge, Mass., 2007.
URL http://www.loc.gov/catdir/toc/ecip079/2007000951.html
[5] N. Landwehr, A. Passerini, L. De Raedt, P. Frasconi, Fast learning of
relational kernels, Machine learning 78 (3) (2010) 305–342.

51

[6] B. Taskar, C. Guestrin, D. Koller, Max-margin Markov networks, in:
S. Thrun, L. Saul, B. Schölkopf (Eds.), Proceedings of Neural Information Processing Systems, MIT Press, Cambridge, MA, 2003, pp. 25–32.
[7] M. Richardson, P. Domingos, Markov logic networks, Machine Learning
62 (2006) 107–136.
[8] N. Friedman, L. Getoor, D. Koller, A. Pfeffer, Learning probabilistic
relational models, in: International Joint Conference on Artificial Intelligence, 1999, pp. 1300–1309.
[9] L. De Raedt, Logical and relational learning, 1st Edition, Cognitive
technologies, Springer, New York, 2008.
[10] D. Heckerman, C. Meek, D. Koller, Probabilistic entity-relationship
models, PRMs, and plate models, in: L. Getoor, B. Taskar (Eds.), Introduction to Statistical Relational Learning, The MIT Press, 2007, pp.
201–238.
[11] F. Costa, K. De Grave, Fast neighborhood subgraph pairwise distance
kernel, in: Proc. of the 27th International Conference on Machine Learning (ICML 2010), 2010, pp. 255–262.
[12] I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun, Large margin
methods for structured and interdependent output variables, Journal of
Machine Learning Research 6 (2) (2006) 1453–1484.
[13] A. Y. Ng, M. I. Jordan, On discriminative vs. generative classifiers:
A comparison of logistic regression and naive bayes, in: T. Dietterich,
S. Becker, Z. Ghahramani (Eds.), Advances in Neural Information Processing Systems (NIPS) 14, 2002, pp. 841–848.
[14] C. Sutton, A. McCallum, An introduction to conditional random fields
for relational learning, in: Getoor and Taskar [4], pp. 93–127.
URL http://www.loc.gov/catdir/toc/ecip079/2007000951.html
[15] Y. Altun, I. Tsochantaridis, T. Hofmann, Hidden markov support vector
machines, in: Twentieth International Conference on Machine Learning
(ICML 2003), 2003, pp. 3–10.

52

[16] K. Lari, S. Young, Applications of stochastic context-free grammars
using the inside-outside algorithm, Computer speech & language 5 (3)
(1991) 237–257.
[17] S. Muggleton, Stochastic logic programs, in: L. De Raedt (Ed.), Advances in Inductive Logic Programming, IOS Press, 1996, pp. 254–264.
[18] B. Taskar, P. Abbeel, D. Koller, Discriminative probabilistic models for
relational data, in: A. Darwiche, N. Friedman (Eds.), Proceedings of
the 18th Conference on Uncertainty in Artificial Intelligence, Morgan
Kaufmann, San Fransisco, CA, 2002, pp. 895–902.
[19] A. Serebrenik, T. Schrijvers, B. Demoen, Improving Prolog programs:
Refactoring for Prolog, Theory and Practice of Logic Programming 8 (2)
(2008) 201–215.
[20] A. Argyriou, T. Evgeniou, M. Pontil, Convex multi-task feature learning, Machine Learning 73 (3) (2008) 243–272.
[21] V. S. Costa, R. Rocha, L. Damas, The Yap Prolog system, Theory and
Practice of Logic Programming 12 (1-2) (2012) 5–34.
[22] C.-C. Chang, C.-J. Lin, LIBSVM: a library for support vector machines,
software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm
(2001).
[23] L. Bottou, Large-scale machine learning with stochastic gradient descent, in: Y. Lechevallier, G. Saporta (Eds.), Proceedings of the
19th International Conference on Computational Statistics (COMPSTAT’2010), Springer, Paris, France, 2010, pp. 177–187.
[24] A. Srinivasan, S. H. Muggleton, R. King, M. Sternberg, Mutagenesis:
ILP experiments in a non-determinate biological domain, in: Proceedings of the 4th International Workshop on Inductive Logic Programming,
volume 237 of GMD-Studien, 1994, pp. 217–232.
[25] R. Wang, Y. Fu, L. Lai, A new atom-additive method for calculating
partition coefficients, J. Chem. Inf. Comput. Sci 37 (3) (1997) 615–621.
[26] T. Evgeniou, C. Micchelli, M. Pontil, Learning multiple tasks with kernel
methods, Journal of Machine Learning Research 6 (1) (2006) 615–637.
53

[27] M. Craven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell,
K. Nigam, S. Slattery, Learning to extract symbolic knowledge from
the world wide web (1998).
[28] G. H. Bakir, T. Hofmann, B. Schölkopf, A. J. Smola, B. Taskar, S. V. N.
Vishwanathan (Eds.), Predicting Structured Data, Neural Information
Processing, The MIT Press, 2007.
[29] T. Joachims, Learning to Classify Text using Support Vector Machines:
Methods, Theory, and Algorithms, Kluwer Academic Publishers, Dordrecht, 2002.
[30] J. Neville, D. Jensen, Collective classification with relational dependency
networks, in: Workshop on Multi-Relational Data Mining (MRDM2003), 2003.
[31] P. Frasconi, M. Jaeger, A. Passerini, Feature discovery with type extension trees, in: Proc. of the 18th Int. Conf. on Inductive Logic Programming, Springer, 2008, pp. 122–139.
[32] A. Vazquez, A. Flammini, A. Maritan, A. Vespignani, Global protein
function prediction from protein-protein interaction networks, Nature
biotechnology 21 (6) (2003) 697–700.
[33] G. Lanckriet, M. Deng, N. Cristianini, M. Jordan, W. Noble, Kernelbased data fusion and its application to protein function prediction
in yeast, in: Proceedings of the Pacific Symposium on Biocomputing,
Vol. 9, 2004, pp. 300–311.
[34] T. G. Dietterich, R. H. Lathrop, T. Lozano-Pérez, Solving the multiple instance problem with axis-parallel rectangles, Artificial Intelligence
89 (1-2) (1997) 31–71.
[35] D. Koller, N. Friedman, Probabilistic graphical models: principles and
techniques, Adaptive computation and machine learning, MIT Press,
Cambridge, MA, 2009.
[36] P. Frasconi, M. Gori, A. Sperduti, A general framework for adaptive
processing of data structures, IEEE Transactions on Neural Networks
9 (5) (1998) 768–786.

54

[37] T. Horváth, T. Gärtner, S. Wrobel, Cyclic pattern kernels for predictive
graph mining, in: Proceedings of KDD 04, ACM Press, 2004, pp. 158–
167.
[38] L. Ralaivola, S. Swamidass, H. Saigo, P. Baldi, Graph kernels for chemical informatics, Neural Networks 18 (8) (2005) 1093–1110.
[39] P. Mahe, N. Ueda, T. Akutsu, J. Perret, J. Vert, Graph kernels for
molecular structure-activity relationship analysis with support vector
machines, J. Chem. Inf. Model 45 (4) (2005) 939–51.
[40] T. Gärtner, Kernels for structured data, Vol. 72 of Series in machine
perception and artificial intelligence, World Scientific, Singapore, 2008.
[41] S. V. N. Vishwanathan, N. N. Schraudolph, R. Kondor, K. M. Borgwardt, Graph kernels, J. Mach. Learn. Res. 99 (2010) 1201–1242.
[42] N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, K. M.
Borgwardt, Weisfeiler-lehman graph kernels, The Journal of Machine
Learning Research 12 (2011) 2539–2561.
[43] B. D. McKay, Practical graph isomorphism, Congressus Numerantium
30 (1981) 45–87.
[44] X. Yan, J. Han., gSpan: Graph-based substructure pattern mining, in:
Proc. 2002 Int. Conf. Data Mining (ICDM ´02), 2002, pp. 721–724.
[45] E. M. Luks, Isomorphism of graphs of bounded valence can be tested in
polynomial time, J. Comput. Syst. Sci 25 (1982) 42–65.
[46] S. Sorlin, C. Solnon, A parametric filtering algorithm for the graph
isomorphism problem, Constraints 13 (2008) 518–537.
[47] S. Menchetti, F. Costa, P. Frasconi, Weighted decomposition kernels,
in: L. De Raedt, S. Wrobel (Eds.), Proceedings of the 22nd International Conference on Machine Learning, Vol. 119 of ACM International
Conference Proceeding Series, ACM, New York, NY, 2005, pp. 585–592.
[48] Z. Kou, W. Cohen, Stacked graphical models for efficient inference in
markov random fields, in: Proceedings of the Seventh SIAM International Conference on Data Mining, 2007, pp. 533–538.
55

[49] H. van de Waterbeemd, E. Gifford, ADMET in silico modelling: towards
prediction paradise?, Nat Rev Drug Discov 2 (3) (2003) 192–204.
[50] C. Helma, S. Kramer, A survey of the predictive toxicology challenge
2000–2001, Bioinformatics 19 (10) (2003) 1179–1182.
[51] C. Helma, Predictive Toxicology, 1st Edition, CRC Press, 2005.
[52] A. Ceroni, F. Costa, P. Frasconi, Classification of small molecules
by two-and three-dimensional decomposition kernels, Bioinformatics
23 (16) (2007) 2038–2045.
[53] J. Kazius, R. McGuire, R. Bursi, Derivation and validation of toxicophores for muta- genicity prediction, J. Med. Chem 48 (1) (2005)
312–320.
[54] H. Blockeel, S. Dzeroski, B. Kompare, S. Kramer, B. Pfahringer,
W. Laer, Experiments in Predicting Biodegradability., Applied Artificial
Intelligence 18 (2) (2004) 157–181.
[55] H. Y. Ando, L. Dehaspe, W. Luyten, E. V. Craenenbroeck, H. Vandecasteele, L. V. Meervelt, Discovering H-Bonding Rules in Crystals with
Inductive Logic Programming, Mol. Pharm. 3 (6) (2006) 665–674.
[56] K. De Grave, F. Costa, Molecular graph augmentation with rings and
functional groups, Journal of Chemical Information and Modeling 50 (9)
(2010) 1660–1668.
[57] D. Wolpert, Stacked generalization, Neural networks 5 (2) (1992) 241–
259.
[58] L. De Raedt, A perspective on inductive databases, SIGKDD Explorations 4 (2) (2002) 69–77.
[59] J.-F. Boulicaut, B. Jeudy, Constraint-based data mining, in: O. Maimon, L. Rokach (Eds.), Data Mining and Knowledge Discovery Handbook, 2nd Edition, Springer, 2010, pp. 339–354.
[60] T. Mitchell, The discipline of machine learning, Tech. Rep. CMU-ML06- 108, Carnegie-Mellon University (2006).

56

[61] L. De Raedt, S. Nijssen, Towards programming languages for machine
learning and data mining (extended abstract), in: Marzena Kryszkiewicz
and Henryk Rybinski and Andrzej Skowron and Zbigniew W. Ras (Ed.),
Foundations of Intelligent Systems - 19th International Symposium, ISMIS 2011, Warsaw, Poland, June 28-30, 2011. Proceedings, Vol. 6804 of
Lecture Notes in Computer Science, Springer, 2011, pp. 25–32.
[62] N. Rizzolo, D. Roth, Learning based java for rapid development of nlp
systems, in: Nicoletta Calzolari and Khalid Choukri and Bente Maegaard and Joseph Mariani and Jan Odijk and Stelios Piperidis and Mike
Rosner and Daniel Tapias (Ed.), Proceedings of the International Conference on Language Resources and Evaluation, LREC 2010, 17-23 May
2010, Valletta, Malta, 2010.
[63] D. Lowd, P. Domingos, Efficient weight learning for markov logic networks, in: Knowledge Discovery in Databases: PKDD 2007, Springer,
2007, pp. 200–211.
[64] S. A. Macskassy, F. Provost, A simple relational classifier, in: Proc. of
the 2nd Workshop on Multi-Relational Data Mining, 2003.
[65] S. Muggleton, Inverse entailment and Progol, New Generation Computing 13 (3–4) (1995) 245–286.
[66] A. Srinivasan, The Aleph Manual (2007).
URL http://www.comlab.ox.ac.uk/activities/machinelearning/
Aleph/
[67] H. Blockeel, L. De Raedt, Top-down induction of first order logical decision trees, Artificial Intelligence 101 (1-2) (1998) 285–297.
[68] M. Bröcheler, L. Mihalkova, L. Getoor, Probabilistic similarity logic, in:
Proc. of the 26th Conference on Uncertainty in Artificial Intelligence
(UAI 2010), 2010.
[69] K. Kersting, L. De Raedt, Bayesian logic programming: theory and
tool, in: L. Getoor, B. Taskar (Eds.), An Introduction to Statistical
Relational Learning, MIT Press, 2007, pp. 291–321.

57

[70] L. De Raedt, A. Kimmig, H. Toivonen, ProbLog: A probabilistic Prolog
and its application in link discovery, in: Proceedings of the 20th international joint conference on artificial intelligence, 2007, pp. 2462–2467.
[71] K. Kersting, Lifted probabilistic inference, in: Proceedings of the 20th
European Conference on Artificial Intelligence, Vol. 242 of Frontiers in
Artificial Intelligence and Applications, IOS Press, 2012, pp. 33–38.
[72] K. Kersting, B. Ahmadi, S. Natarajan, Counting belief propagation, in:
Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial
Intelligence, UAI ’09, AUAI Press, Arlington, Virginia, United States,
2009, pp. 277–284.
[73] T. Gärtner, A survey of kernels for structured data., SIGKDD Explorations 5 (1) (2003) 49–58.
[74] G. Wachman, R. Khardon, Learning from interpretations: a rooted kernel for ordered hypergraphs, in: Proceedings of the 24th international
conference on Machine learning, 2007, pp. 943–950.
[75] S. Kramer, N. Lavrač, P. Flach, Propositionalization approaches to relational data mining, in: S. Džeroski, N. Lavrač (Eds.), Relational Data
Mining, Springer, 2001, pp. 262–291.
[76] J. R. Quinlan, Learning logical definitions from relations, Machine
Learning 5 (1990) 239–266.
[77] R. A. Rossi, L. K. McDowell, D. W. Aha, J. Neville, Transforming graph
data for statistical relational learning, Journal of Artificial Intelligence
Research 45 (1) (2012) 363–441.
[78] N. Lao, W. W. Cohen, Relational retrieval using a combination of pathconstrained random walks, Machine learning 81 (1) (2010) 53–67.
[79] D. J. Cook, L. B. Holder, Mining graph data, Wiley-Interscience, 2006.
[80] Y. Sun, J. Han, Mining heterogeneous information networks: principles
and methodologies, Synthesis Lectures on Data Mining and Knowledge
Discovery 3 (2) (2012) 1–159.
[81] M. Chang, L. Ratinov, N. Rizzolo, D. Roth, Learning and inference with
constraints, in: Proceedings of AAAI, 2008, pp. 1513–1518.
58

[82] A. McCallum, K. Schultz, S. Singh, FACTORIE: Probabilistic programming via imperatively defined factor graphs, in: Neural Information
Processing Systems (NIPS), 2009, pp. 1249–1257.
[83] M. Verbeke, V. Van Asch, R. Morante, P. Frasconi, W. Daelemans,
L. De Raedt, A statistical relational learning approach to identifying
evidence based medicine categories, in: Proc. of EMNLP-CoNLL, 2012,
pp. 579–589.
[84] B. London, B. Huang, B. Taskar, L. Getoor, Collective stability in structured prediction: Generalization from one example, in: S. Dasgupta,
D. Mcallester (Eds.), Proceedings of the 30th International Conference
on Machine Learning (ICML-13), JMLR Workshop and Conference Proceedings, 2013, pp. 828–836.
URL http://jmlr.org/proceedings/papers/v28/london13.pdf
[85] A. Kimmig, B. Demoen, L. De Raedt, V. S. Costa, R. Rocha, On the implementation of the probabilistic logic programming language problog,
Theory and Practice of Logic Programming 11 (2-3) (2011) 235–262.
[86] M. Verbeke, P. Frasconi, V. Van Asch, R. Morante, W. Daelemans, L. De
Raedt, Kernel-based logical and relational learning with klog for hedge
cue detection, in: H. Muggleton, S. amd Watanabe, J. TamaddoniNezhad A., Chen (Eds.), Inductive Logic Programming: Revised Selected Papers from the 21st International Conference (ILP 2011), Lecture Notes in Artificial Intelligence, 2012, pp. 347–357.
[87] P. Kordjamshidi, P. Frasconi, M. Van Otterlo, M. Moens, L. De Raedt,
Spatial relation extraction using relational learning, in: H. Muggleton,
S. amd Watanabe, J. Tamaddoni-Nezhad A., Chen (Eds.), Inductive
Logic Programming: Revised Selected Papers from the 21st International Conference (ILP 2011), Lecture Notes in Artificial Intelligence,
2012, pp. 204–220.
[88] L. Antanas, P. Frasconi, F. Costa, T. Tuytelaars, L. De Raedt, A relational kernel-based framework for hierarchical image understanding, in:
G. L. Gimel’farb, E. R. Hancock, A. I. Imiya, A. Kuijper, M. Kudo,
S. Shinichiro Omachi, T. Windeatt, K. Yamada (Eds.), Lecture Notes
in Computer Science„ Springer, 2012, pp. 171–180.

59

[89] L. Antanas, M. Hoffmann, P. Frasconi, T. Tuytelaars, L. D. Raedt,
A relational kernel-based approach to scene classification, in: WACV,
2013, pp. 133–139.
[90] L. Antanas, P. Frasconi, T. Tuytelaars, L. De Raedt, Employing logical
languages for image understanding, IEEE Workshop on Kernels and
Distances for Computer Vision, International Conference on Computer
Vision, Barcelona, Spain, 13 November 2011 (Nov. 2011).
[91] J. L. Gross, J. Yellen, Graph Theory and Its Applications, Second
Edition (Discrete Mathematics and Its Applications), Chapman &
Hall/CRC, 2005.
[92] D. Haussler, Convolution kernels on discrete structures, Tech. Rep. 9910, UCSC-CRL (1999).
[93] Q. Shi, J. Petterson, G. Dror, J. Langford, A. Smola, S. Vishwanathan,
Hash kernels for structured data, Journal of Machine Learning Research
10 (2009) 2615–2637.
[94] K. De Grave, Predictive quantitative structure-activity relationship
models and their use for the efficient screening of molecules, Ph.D. thesis, Katholieke Universiteit Leuven (August 2011).

60

