skip to main content
10.1145/1141277.1141416acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
Article

Effective rule induction from labeled graphs

Published: 23 April 2006 Publication History

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.

References

[1]
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, Reading, Mass., 1995.]]
[2]
C. Anglano, A. Giordana, G. Lo Bello, and L. Saitta. An experimental evaluation of coevolutive concept learning. Proc. of the 15th Int. Conf. on Machine Learning, pp. 19--27, Morgan Kaufmann, 1998.]]
[3]
W. Cohen and Y. Singer. A Simple, Fast, and Effective Rule Learner. Proc. of 16th National Conf. on Artificial Intelligence, pp. 335--342, AAAI Press, 1999.]]
[4]
H.-D. Ebbinghaus and J. Flum. Finite Model Theory Springer, Berlin, 1995.]]
[5]
R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. Journal of the ACM, 30(3):514--550, 1983.]]
[6]
Y. Freund, and R. E. Schapire. Experiments with a New Boosting Algorithm. Proc. of 13th Int. Conf. on Machine Learning, pp. 148--156, Morgan Kaufmann, 1996.]]
[7]
P. M. Gleiss and P. F. Stadler. Relevant cycles in biopolymers and random graph. In Proc. of the 4th Slovene Int. Conf. in Graph Theory, 1999.]]
[8]
G. Gottlob, N. Leone, and F. Scarcello. The complexity of acyclic conjunctive queries. Journal of the ACM, 48(3):431--498, 2001.]]
[9]
M. Graham. On the universal relation. Technical report, Univ. of Toronto, Toronto, Canada, 1979.]]
[10]
K. Hirata. On the hardness of learning acyclic conjunctive queries. In Proc. of the 11th International Conference on Algorithmic Learning Theory, pp. 238--251. Springer, Berlin, 2000.]]
[11]
S. Hoche and S. Wrobel. Relational Learning Using Constrained Confidence-Rated Boosting. Proc. 11th Int. Conf. on Inductive Logic Programming, pp. 51--64, Springer, Berlin, 2001.]]
[12]
T. Horváth, T. Gärtner, and S. Wrobel. Cyclic Pattern Kernels for Predictive Graph Mining. In Proc. of the 10th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 158--167. ACM Press, New York, NY, 2004.]]
[13]
T. Horváth and G. Turán. Learning logic programs with structured background knowledge. Artificial Intelligence, 128(1--2):31--97, 2001.]]
[14]
T. Horváth and S. Wrobel. Toward Discovery of Deep and Wide First-Order Structures: A Case Study in the Domain of Mutagenicity. Proc. of Discovery Science, pp. 100--112, Springer, Berlin, 2001.]]
[15]
A. Karalic. First Order Regression. PhD thesis, University of Ljubljana, Faculty of Computer Science, Ljubljana, Slovenia, 1995.]]
[16]
P. G. Kolaitis and M. Y. Vardi. Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences, 61(2):302--332, 2000.]]
[17]
S. Muggleton and L. De Raedt. Inductive logic programming: Theory and methods. The Journal of Logic Programming, 19/20:629--680, 1994.]]
[18]
S.-H. Nienhuys-Cheng and R. de Wolf. Foundations of Inductive Logic Programming, volume 1228 of LNAI, Springer, Berlin, 1997.]]
[19]
D. Opitz, and R. Maclin. Popular Ensemble Method: An Empirical Study. Journal of Artificial Intelligence Research, 11:169--198, 1999.]]
[20]
M. Plotkin. Mathematical basis of ring-finding algorithms at CIDS. J. Chem. Doc., 11:60--63, 1971.]]
[21]
J. R. Quinlan. Bagging, boosting, and C4.5. Proc. of 14th National Conf. on Artificial Intelligence, pp. 725--730, AAAI Press, 1996.]]
[22]
R. E. Schapire, and Y. Singer. Improved boosting algorithms using confidence-rated predictions. Proc. of the 11th Annual Conf. on Computational Learning Theory, pp. 80--91, ACM Press, 1998.]]
[23]
M. Sebag. Distance Induction in First Order Logic. Proc. 7th Int. Workshop on Inductive Logic Programming, pp. 264--272, Springer, 1997.]]
[24]
A. Srinivasan, S. Muggleton, and R. King. Comparing the use of background knowledge by inductive logic programming systems. Proc. of the 5th Int. Workshop on Inductive Logic Programming, 1995.]]
[25]
A. Srinivasan, S. Muggleton, M. J. E. Sternberg, and R. D. King. Theories for mutagenicity: A study in first-order and feature-based induction. Artificial Intelligence, 85:277--299, 1996.]]
[26]
P. Vismara. Union of all the minimum cycle bases of a graph. The Electronic Journal of Combinatorics, 4(1):73--87, 1997.]]
[27]
S. Wrobel. Inductive logic programming. In G. Brewka, editor, Advances in Knowledge Representation and Reasoning, pp. 153--189. CSLI-Publishers, Stanford, CA, 1996. Studies in Logic, Language and Information.]]
[28]
M. Yannakakis. Algorithms for acyclic database schemes. In Proc. of the 7th Conf. on Very Large Databases, pp. 82--94, Morgan Kaufman, 1981.]]
[29]
C. T. Yu and Z. M. Ozsoyoglu. On determining tree query membership of a distributed query. INFOR, 22(3), 1984.]]

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SAC '06: Proceedings of the 2006 ACM symposium on Applied computing
April 2006
1967 pages
ISBN:1595931082
DOI:10.1145/1141277
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. computational chemistry
  2. graph mining

Qualifiers

  • Article

Conference

SAC06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25
The 40th ACM/SIGAPP Symposium on Applied Computing
March 31 - April 4, 2025
Catania , Italy

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 267
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media