Abstract
Learning from complex data is becoming increasingly important, and graph kernels have recently evolved into a rapidly developing branch of learning on structured data. However, previously proposed kernels rely on having discrete node label information. In this paper, we explore the power of continuous node-level features for propagation-based graph kernels. Specifically, propagation kernels exploit node label distributions from propagation schemes like label propagation, which naturally enables the construction of graph kernels for partially labeled graphs. In order to efficiently extract graph features from continuous node label distributions, and in general from continuous vector-valued node attributes, we utilize randomized techniques, which easily allow for deriving similarity measures based on propagated information. We show that propagation kernels utilizing locality-sensitive hashing reduce the runtime of existing graph kernels by several orders of magnitude. We evaluate the performance of various propagation kernels on real-world bioinformatics and image benchmark datasets.
Chapter PDF
Similar content being viewed by others
Keywords
- Benchmark Dataset
- Neural Information Processing System
- Label Propagation
- Hellinger Distance
- Quantization Function
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ahmadi, B., Kersting, K., Sanner, S.: Multi-Evidence Lifted Message Passing, with Application to PageRank and the Kalman Filter. In: Proc. of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 (2011)
Borgwardt, K.M., Kriegel, H.-P.: Shortest-path kernels on graphs. In: Proceedings of International Conference on Data Mining (ICDM 2005), pp. 74–81 (2005)
Datar, M., Indyk, P.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the 20th Annual Symposium on Computational Geometry (SCG 2004), pp. 253–262 (2004)
Gärtner, T., Flach, P.A., Wrobel, S.: On Graph Kernels: Hardness Results and Efficient Alternatives. In: Schölkopf, B., Warmuth, M.K. (eds.) COLT/Kernel 2003. LNCS (LNAI), vol. 2777, pp. 129–143. Springer, Heidelberg (2003)
Gersho, A., Gray, R.: Vector quantization and signal compression. Kluwer Academic Publishers, Norwell (1991)
Hido, S., Kashima, H.: A linear-time graph kernel. In: Proc. of the 9th IEEE International Conference on Data Mining (ICDM 2009), pp. 179–188 (2009)
Horváth, T., Gärtner, T., Wrobel, S.: Cyclic pattern kernels for predictive graph mining. In: Proceedings of Knowledge Discovery in Databases (KDD 2004), pp. 158–167 (2004)
Jaakkola, T., Haussler, D.: Exploiting generative models in discriminative classifiers. In: Proc. of Neural Information Processing Systems (NIPS 1998), pp. 487–493 (1998)
Jebara, T., Kondor, R.I., Howard, A.: Probability product kernels. Journal of Machine Learning Research 5, 819–844 (2004)
Kashima, H., Tsuda, K., Inokuchi, A.: Marginalized kernels between labeled graphs. In: Proc. of the 20th International Conference on Machine Learning (ICML 2003), pp. 321–328 (2003)
Kersting, K., Ahmadi, B., Natarajan, S.: Counting Belief Propagation. In: Proc. of the 25th Conference on Uncertainty in Artificial Intelligence, UAI 2009 (2009)
Lafferty, J.D., Lebanon, G.: Information diffusion kernels. In: Proc. of Neural Information Processing Systems (NIPS 2002), pp. 375–382 (2002)
Mahé, P., Vert, J.-P.: Graph kernels based on tree patterns for molecules. Machine Learning 75(1), 3–35 (2009)
Moreno, P.J., Ho, P., Vasconcelos, N.: A Kullback-Leibler Divergence Based Kernel for SVM Classification in Multimedia Applications. In: Proc. of Neural Information Processing Systems, NIPS 2003 (2003)
Neumann, M., Kersting, K., Ahmadi, B.: Markov logic sets: Towards lifted information retrieval using pagerank and label propagation. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI 2011 (2011)
Ramon, J., Gärtner, T.: Expressivity versus efficiency of graph kernels. In: Proceedings of the 1st International Workshop on Mining Graphs, Trees and Sequences, pp. 65–74 (2003)
Richardson, M., Domingos, P.: Markov logic networks. Machine Learning 62(1-2), 107–136 (2006)
Shervashidze, N., Schweitzer, P., van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler–Lehman Graph Kernels. Journal of Machine Learning Research 12, 2539–2561 (2011)
Shervashidze, N., Vishwanathan, S.V.N., Petri, T., Mehlhorn, K., Borgwardt, K.M.: Efficient graphlet kernels for large graph comparison. Journal of Machine Learning Research - Proceedings Track 5, 488–495 (2009)
Singla, P., Domingos, P.: Lifted First-Order Belief Propagation. In: Proc. of the 23rd AAAI Conf. on Artificial Intelligence (AAAI 2008), pp. 1094–1099 (2008)
Tsuda, K., Kawanabe, M., Rätsch, G., Sonnenburg, S., Müller, K.-R.: A new discriminative kernel from probabilistic models. Neural Computation 14(10), 2397–2414 (2002)
Vishwanathan, S.V.N., Schraudolph, N.N., Kondor, R.I., Borgwardt, K.M.: Graph kernels. Journal of Machine Learning Research 11, 1201–1242 (2010)
Yedidia, J.S., Freeman, W.T., Weiss, Y.: Generalized belief propagation. In: Proc. of Neural Information Processing Systems (NIPS 2000), pp. 689–695 (2000)
Zhou, D., Bousquet, O., Lal, T.N., Weston, J., Schölkopf, B.: Learning with local and global consistency. In: Proc. of Neural Information Processing Systems, NIPS 2009 (2003)
Zhu, X., Ghahramani, Z.: Learning from labeled and unlabeled data with label propagation. Technical report, CMU-CALD-02-107. Carnegie Mellon University (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Neumann, M., Patricia, N., Garnett, R., Kersting, K. (2012). Efficient Graph Kernels by Randomization. In: Flach, P.A., De Bie, T., Cristianini, N. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2012. Lecture Notes in Computer Science(), vol 7523. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33460-3_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-33460-3_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33459-7
Online ISBN: 978-3-642-33460-3
eBook Packages: Computer ScienceComputer Science (R0)