Labeled graphs provide a natural way of representing objects and the way they are connected. They have various applications in different fields, such as for example in computational chemistry. They can be represented by relational structures and thus stored in relational databases. Acyclic conjunctive queries form a practically relevant fragment of database queries that can be evaluated in polynomial time. We propose a top-down induction algorithm for learning acyclic conjunctive queries from labeled graphs represented by relational structures. The algorithm allows the use of building blocks which depend on the particular application considered. To compensate for the reduced expressive power of the hypothesis language and thus the potential loss in predictive performance, we combine acyclic conjunctive queries with confidence-rated boosting. In the empirical evaluation of the method we show that it leads to excellent prediction accuracy on the domain of mutagenicity.
|Translated title of the contribution||Effective rule induction from labeled graphs|
|Title of host publication||Association for Computing Machinery: Proceedings of the ACM Symposium on Applied Computing : SAC 2006, April 23-27, 2006, Dijon, France|
|Publisher||Association for Computing Machinery (ACM)|
|Publication status||Published - 2006|
Bibliographical noteOther page information: 611-616
Conference Proceedings/Title of Journal: Association for Computing Machinery: Proceedings of the ACM Symposium on Applied Computing : SAC 2006, April 23-27, 2006, Dijon, France
Other identifier: 2000565