Maximum Common Subgraph based locally weighted regression
Authors: 
Madeleine Seeland, Fabian Buchwald, Stefan Kramer, Bernhard PfahringerAuthors Info & Claims
Pages 165 - 172
Abstract
This paper investigates a simple, yet effective method for regression on graphs, in particular for applications in chem-informatics and for quantitative structure-activity relationships (QSARs). The method combines Locally Weighted Learning (LWL) with Maximum Common Subgraph (MCS) based graph distances. More specifically, we investigate a variant of locally weighted regression on graphs (structures) that uses the maximum common subgraph for determining and weighting the neighborhood of a graph and feature vectors for the actual regression model. We show that this combination, LWL-MCS, outperforms other methods that use the local neighborhood of graphs for regression. The performance of this method on graphs suggests it might be useful for other types of structured data as well.
References
[1]
E. Alphonse, T. Girschick, F. Buchwald, and S. Kramer. A numerical refinement operator based on multi-instance learning. In Proceedings of the 20th International Conference on Inductive Logic Programming, pages 14--21. Springer, 2011.
[2]
C. Atkeson, A. Moore, and S. Schaal. Locally weighted learning. AI Review, 11: 11--73, 1997.
[3]
S. Bickel and T. Scheffer. Multi-view clustering. In Proceedings of the Fourth IEEE International Conference on Data Mining, ICDM '04, pages 19--26, Washington, DC, USA, 2004. IEEE Computer Society.
[4]
F. Buchwald, T. Girschick, M. Seeland, and S. Kramer. Using local models to improve (Q)SAR predictivity. Molecular Informatics, 30(2--3): 205--218, 2011.
[5]
Y. Cao, T. Jiang, and T. Girke. A maximum common substructure-based algorithm for searching and predicting drug-like compounds. Bioinformatics, 24(13): i366--i374, 2008.
[6]
W. Cleveland. Robust locally weighted regression and smoothing scatterplots. Journal of the American Statistical Association, 74: 829--836, 1979.
[7]
D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, pages 265--298, 2004.
[8]
L. De Raedt. Logical and Relational Learning. Springer, 2008.
[9]
T. Gärtner. Kernels for Structured Data. PhD thesis, Universität Bonn, 2005.
[10]
M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The WEKA data mining software: an update. SIGKDD Explorations, 11(1): 10--18, 2009.
[11]
M. Kloft, U. Rückert, and P. L. Bartlett. A unifying view of multiple kernel learning. In Proceedings of the 2010 European Conference on Machine Learning and Knowledge Discovery in Databases, pages 66--81, 2010.
[12]
Y. C. Martin, J. L. Kofron, and L. M. Traphagen. Do structurally similar molecules have similar biological activity? Journal of Medicinal Chemistry, 45(19): 4350--4358, 2002.
[13]
U. Rückert, T. Girschick, F. Buchwald, and S. Kramer. Adapted transfer of distance measures for quantitative structure-activity relationships. In Proceedings of the 13th International Conference on Discovery Science, DS'10, pages 341--355, 2010.
[14]
S. Rüping. Globalization of local models with SVMs. In LeGo-08 - From Local Patterns to Global Models, Workshop at ECML/PKDD, 2008.
[15]
L. Schietgat, F. Costa, J. Ramon, and L. De Raedt. Effective feature construction by maximum common subgraph sampling. Machine Learning, 83: 137--161, 2011.
[16]
M. Seeland, S. A. Berger, A. Stamatakis, and S. Kramer. Parallel structural graph clustering. In Proceedings of the 2011 European conference on Machine learning and knowledge discovery in databases, ECML PKDD '11, pages 256--272, 2011.
[17]
K. Tsuda. Support vector classifier with asymmetric kernel functions. In Proceedings of the Seventh European Symposium on Artificial Neural Networks, ESANN'99, pages 183--188, 1999.
[18]
W. D. Wallis, P. Shoubridge, M. Kraetz, and D. Ray. Graph distances using graph union. Pattern Recognition Letters, 22: 701--704, 2001.
Recommendations
Approximating the maximum common subgraph isomorphism problem with a weighted graph
The maximum common subgraph isomorphism problem is a difficult graph problem, and the problem of finding the maximum common subgraph isomorphism problem is NP-hard. This means there is likely no algorithm that will be able to find the maximal isomorphic ...
Mean and maximum common subgraph of two graphs
A mean of a pair of graphs, g1 and g2, is formally defined as a graph that minimizes the sum of edit distances to g1 and g2. The edit distance of two graphs g and g' is the minimum cost taken over all sequences of edit operations that transform g into g'...
Using locally weighted learning to improve SMOreg for regression
PRICAI'06: Proceedings of the 9th Pacific Rim international conference on Artificial intelligenceShevade et al.[1] are successful in extending some improved ideas to Smola and Scholkopf's SMO algorithm[2] for solving regression problems, simply named SMOreg. In this paper, we use SMOreg in exactly the same way as linear regression(LR) is used in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2012
2179 pages
Copyright © 2012 ACM.
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: 26 March 2012
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SAC 2012
Sponsor:
Acceptance Rates
SAC '12 Paper Acceptance Rate 270 of 1,056 submissions, 26%;
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Upcoming Conference
SAC '25
- Sponsor:
- sigapp
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 147Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in