09:30-13:00 |
T1. Structural Decomposition Methods: Identifying easy
instances of hard problems
[abstract]
Francesco Scarcello and Gianluigi Greco |

15:00-18:30 |
T2. Multivariate Models for Relational Learning
[abstract]Volker Tresp |

Many NP-hard problems in different application areas, ranging, e.g., from AI and Database Theory to Game theory, are known to be efficiently solvable when restricted to instances whose underlying structures can be modelled via acyclic graphs or hypergraphs. However, structures arising from real applications are hardly precisely acyclic. Yet, they are often not very intricate and, in fact, tend to exhibit some limited degree of cyclicity, which suffices to retain most of the nice properties of acyclic ones. Therefore, several efforts have been spent to investigate invariants that are best suited to identify nearly-acyclic graph/hypergraphs, leading to the definition of a number of so-called structural decomposition methods.

The tutorial will illustrate the main structural decomposition methods proposed in the literature within a unifying framework, it will discuss their game-theoretic and logical characterizations, and it will present the algorithmic approaches that can be used to efficiently solve nearly acyclic instances, by looking at the so-called islands of tractability. As a reference scenario for the exposition, the well-known problem of efficiently evaluating conjunctive queries in relational databases will be considered.

The tutorial is intended both for academic researchers and for implementers, wishing to familiarize with methods and algorithms tailored to efficiently solve NP-hard problems. The tutorial will be self-contained. No specific prerequisites are required.

Multivariate modeling concerns the prediction of several response variables given the inputs. The main motivation behind multivariate modeling is that, via combined modeling, the prediction accuracy for each individual response variable is improved. In the first half of the tutorial, we will cover some of the main approaches to multivariate modeling, e.g., hierarchical Bayesian modeling, mixed models, projection methods, matrix decomposition, and structural prediction. The second half of the tutorial is concerned with the application of multivariate models to relational learning. Examples include the infinite hidden relational model, stochastic relational models, and multivariate models used in Semantic Web computing.

We believe that this area of research is of major interest and should attract a wide audience. Technically, only basic knowledge in probability and machine learning is assumed.