Effective rule induction from labeled graphs

Horvath Tamas, Hoche Susanne, Wrobel Stefan

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

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 contributionEffective rule induction from labeled graphs
Original languageEnglish
Title of host publicationAssociation for Computing Machinery: Proceedings of the ACM Symposium on Applied Computing : SAC 2006, April 23-27, 2006, Dijon, France
PublisherAssociation for Computing Machinery (ACM)
Publication statusPublished - 2006

Bibliographical note

Other 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

Fingerprint

Dive into the research topics of 'Effective rule induction from labeled graphs'. Together they form a unique fingerprint.

Cite this