Date of Publication :21st March 2018
Abstract: In the real world all events are connected. There is a hidden network of dependencies that governs behavior of natural processes. Without much argument it can be said that, of all the known data- structures, graphs are naturally suitable to model such information. But to learn to use graph data structure is a tedious job as most operations on graphs are computationally expensive, so exploring fast machine learning techniques for graph data has been an active area of research and a family of algorithms called kernel based approaches has been famous among researchers of the machine learning domain. With the help of support vector machines, kernel based methods work very well for learning with Gaussian processes. In this survey we will explore various kernels that operate on graph representations. Starting from the basics of kernel based learning we will travel through the history of graph kernels from its first appearance to discussion of current state of the art techniques in practice
Reference :
-
- R.R. Dipert, The mathematical structure of the world: The world as graph, J. Philos. 94 (7) (1997) 329–358.
- H. Bunke, Graph-based tools for data mining and machine learning, in: International Workshop on Machine Learning and Data Mining in Pattern Recognition, Springer, 2003, pp. 7–19.
- D. Conte, P. Foggia, C. Sansone, M. Vento, Thirty years of graph matching in pattern recognition, Int. J. Pattern Recognit. Artif. Intell. 18 (03) (2004) 265– 298.
- T. Gärtner, A survey of kernels for structured data, ACM SIGKDD Explor. Newslett. 5 (1) (2003) 49–58.
- S.V.N. Vishwanathan, N.N. Schraudolph, R. Kondor, K.M. Borgwardt, Graph kernels, J. Mach. Learn. Res. 11 (Apr) (2010) 1201–1242.
- N. Shervashidze, Scalable Graph Kernels (Ph.D. thesis), Universität Tübingen, 2012.
- K.M. Borgwardt, Graph Kernels (Ph.D. thesis), lmu, 2007.
- http://dx.doi.org/10.1198/jasa.2003.s269
- N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (3) (1950) 337–404.
- B. Scholkopf, A.J. Smola, Learning With Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, 2002, arXiv: arXiv:1011.1669v3, http://dx.doi.org/10.1198/jasa.2003.s269.
- I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun, A.-C. Org, Large margin methods for structured and interdependent output variables, J. Mach. Learn. Res. 6 (2005) 1453–1484. http://dx.doi.org/10.1007/s10994-008- 5071-9.