Partial least squares regression for graph mining

ABSTRACT

Attributed graphs are increasingly more common in many application domains such as chemistry, biology and text processing. A central issue in graph mining is how to collect informative subgraph patterns for a given learning task. We propose an iterative mining method based on partial least squares regression (PLS). To apply PLS to graph data, a sparse version of PLS is developed first and then it is combined with a weighted pattern mining algorithm. The mining algorithm is iteratively called with different weight vectors, creating one latent component per one mining call. Our method, graph PLS, is efficient and easy to implement, because the weight vector is updated with elementary matrix calculations. In experiments, our graph PLS algorithm showed competitive prediction accuracies in many chemical datasets and its efficiency was significantly superior to graph boosting (gBoost) and the naive method based on frequent graph mining.

REFERENCES

• 1: B. Bringmann, A. Zimmermann, L. D. Raedt, and S. Nijssen. Don't be afraid of simpler patterns. In 10th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD), pages 55--66. Sprinter, 2006.
• 2: Jonathan Chen , S. Joshua Swamidass , Yimeng Dou , Jocelyne Bruand , Pierre Baldi, ChemDB: a public database of small molecules and related chemoinformatics resources, Bioinformatics, v.21 n.22, p.4133-4139, November 2005 [doi>10.1093/bioinformatics/bti683]
• 3: Ayhan Demiriz , Kristin P. Bennett , John Shawe-Taylor, Linear Programming Boosting via Column Generation, Machine Learning, v.46 n.1-3, p.225-254, 2002 [doi>10.1023/A:1012470815092]
• 4: Mukund Deshpande , Michihiro Kuramochi , Nikil Wale , George Karypis, Frequent Substructure-Based Approaches for Classifying Chemical Compounds, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1036-1050, August 2005 [doi>10.1109/TKDE.2005.127]
• 5: L. Eldén. Partial least squares vs. lanczos bidiagonalization i: Analysis of a projection method for multiple regression. Computational Statistics and Data Analysis, 46(1):11--31, 2004.
• 6: H. Fröhrich, J. Wegner, F. Sieker, and Z. Zell. Kernel functions for attributed molecular graphs - a new similarity based approach to ADME prediction in classification and regression. QSAR & Combinatorial Science, 25(4):317--326, 2006.
• 7: C. Helma, T. Cramer, S. Kramer, and L. Raedt. Data mining and machine learning techniques for the identification of mutagenicity inducing substructures and structure activity relationships of noncongeneric compounds. J. Chem. Inf. Comput. Sci., 44:1402--1411, 2004.
• 8: A. Höskuldsson. PLS Regression Methods. Journal of Chemometrics, 2:211--228, 1988.
• 9: Akihiro Inokuchi, Mining Generalized Substructures from a Set of Labeled Graphs, Proceedings of the Fourth IEEE International Conference on Data Mining, p.415-418, November 01-04, 2004
• 10: H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 21st International Conference on Machine Learning, pages 321--328. AAAI Press, 2003.
• 11: J. Kazius, S. Nijssen, J. Kok, and T. B. A. Ijzerman. Substructure mining using elaborate chemical representation. J. Chem. Inf. Model., 46:597--605, 2006.
• 12: Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
• 13: Nicole Krämer , Mikio L. Braun, Kernelizing PLS, degrees of freedom, and efficient model selection, Proceedings of the 24th international conference on Machine learning, p.441-448, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273552]
• 14: Stefan Kramer , Luc De Raedt , Christoph Helma, Molecular feature mining in HIV data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.136-143, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502533]
• 15: T. Kudo, E. Maeda, and Y. Matsumoto. An application of boosting to graph classification. In Advances in Neural Information Processing Systems 17, pages 729--736. MIT Press, 2005.
• 16: P. Mahé, L. Ralaivola, V. Stoven, and J.-P. Vert. The pharmacophore kernel for virtual screening with support vector machines. J. Chem. Inf. Model., 46(5):2003--2014, 2006.
• 17: M. Momma and K. Bennett. Constructing orthogonal latent features for arbitrary loss. Feature Extraction, Foundations and Applications. Springer, 2006.
• 18: Shinichi Morishita, Computing Optimal Hypotheses Efficiently for Boosting, Progress in Discovery Science, Final Report of the Japanese Discovery Science Project, p.471-481, January 2002
• 19: Shinichi Morishita , Jun Sese, Transversing itemset lattices with statistical metric pruning, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.226-236, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335226]
• 20: Siegfried Nijssen , Joost N. Kok, A quickstart in frequent structure mining can make a difference, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014134]
• 21: S. Nowozin, G. Bakir, and K. Tsuda. Discriminative subsequence mining for action classification. In Proceedings of the 11th IEEE International Conference on Computer Vision (ICCV 2007), pages 1919--1923. IEEE Computer Society, 2007.
• 22: S. Nowozin, K. Tsuda, T. Uno, T. Kudo, and G. Bakir. Weighted substructure mining for image analysis. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pages 1--8. IEEE Computer Society, 2007.
• 23: Liva Ralaivola , Sanjay J. Swamidass , Hiroto Saigo , Pierre Baldi, Graph kernels for chemical informatics, Neural Networks, v.18 n.8, p.1093-1110, October 2005 [doi>10.1016/j.neunet.2005.07.009]
• 24: Gunnar Rätsch , Ayhan Demiriz , Kristin P. Bennett, Sparse Regression Ensembles in Infinite and Finite Hypothesis Spaces, Machine Learning, v.48 n.1-3, p.189-218, 2002 [doi>10.1023/A:1013907905629]
• 25: R. Rosipal and N. Krämer. Overview and recent advances in partial least squares. In Subspace, Latent Structure and Feature Selection Techniques, pages 34--51. Springer, 2006.
• 26: H. Saigo, T. Kadowaki, and K. Tsuda. A linear programming approach for molecular QSAR analysis. In International Workshop on Mining and Learning with Graphs (MLG), pages 85--96, 2006.
• 27: Hiroto Saigo , Takeaki Uno , Koji Tsuda, Mining complex genotypic features for predicting HIV-1 drug resistance, Bioinformatics, v.23 n.18, p.2455-2462, September 2007 [doi>10.1093/bioinformatics/btm353]
• 28: A. Sanfeliu and K. Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern., 13:353--362, 1983.
• 29: Koji Tsuda, Entire regularization paths for graph data, Proceedings of the 24th international conference on Machine learning, p.919-926, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273612]
• 30: Koji Tsuda , Taku Kudo, Clustering graphs by weighted substructure mining, Proceedings of the 23rd international conference on Machine learning, p.953-960, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143964]
• 31: K. Tsuda and K. Kurihara. Graph mining with variational dirichlet process mixture models. In SIAM Conference on Data Mining (SDM), 2008. to appear.
• 32: Manfred K. Warmuth , Jun Liao , Gunnar Rätsch, Totally corrective boosting algorithms that maximize the margin, Proceedings of the 23rd international conference on Machine learning, p.1001-1008, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143970]
• 33: H. Wold. Path models with latent variables: The NIPALS approach. In Quantitative Sociology: International Perspectives on Mathematical and Statistical Model Building, pages 307--357. Academic Press, 1975.
• 34: S. Wold, M. Sjöstöm, and L. Erikkson. PLS-regression: a basic tool of chemometrics. Chemometrics and intelligent laboratory systems, 58:109--130, 2001.
• 35: Xifeng Yan , Hong Cheng , Jiawei Han , Philip S. Yu, Mining significant graph patterns by leap search, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376662]
• 36: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Performance

Keywords:
chemoinformatics, graph boosting, graph mining, partial least squares regression