Abstract
In this paper we develop a novel graph kernel by matching the depth-based substructures in graphs. We commence by describing how to compute the Shannon entropy of a graph using random walks. We then develop an h-layer depth-based representations for a graph, which is effected by measuring the Shannon entropies of a family of K-layer expansion subgraphs derived from a vertex of the graph. The depth-based representations characterize graphs in terms of high dimensional depth-based complexity information. Based on the new representation, we establish a possible correspondence between vertices of two graphs that allows us to construct a matching-based graph kernel. Experiments on graphs from computer vision datasets demonstrate the effectiveness of our kernel.
Chapter PDF
Similar content being viewed by others
References
Harchaoui, Z., Bach, F.: Image classification with segmentation graph kernels. In: Proc. CVPR (2007)
Barra, V., Biasotti, S.: 3D shape retrieval using Kernels on Extended Reeb Graphs. Pattern Recognition 46, 2985–2999 (2013)
Shervashidze, N., Schweitzer, P., Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research 1, 1–48 (2010)
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)
Jebara, T., Kondor, R.I., Howard, A.: Probability product kernels. Journal of Machine Learning Research 5, 819–844 (2004)
Haussler, D.: Convolution kernels on discrete structures. In Technical Report UCS-CRL-99-10, UC Santa Cruz (1999)
Borgwardt, K.M., Kriegel, H.P.: Shortest-path kernels on graphs. In: Proc. ICDM, pp. 74–81 (2005)
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 5, 488–495 (2009)
Costa, F., Grave, K.D.: Fast neighborhood subgraph pairwise distance kernel. In: Proc. ICML, pp. 255–262 (2010)
Aziz, F., Wilson, R.C., Hancock, E.R.: Backtrackless walks on a graph. IEEE Trans. Neural Netw. Learning Syst. 24(6), 977–989 (2013)
Ren, P., Wilson, R.C., Hancock, E.R.: Graph characterization via Ihara coefficients. IEEE Transactions on Neural Networks 22(2), 233–245 (2011)
Escolano, F., Hancock, E.R., Lozano, M.A.: Heat diffusion: Thermodynamic depth complexity of networks. Physical Review E 85, 036206 (2012)
Bai, L., Hancock, E.R.: Depth-based complexity traces of graphs. Pattern Recognition 47(3), 1172–1186 (2014)
Dehmer, M., Mowshowitz, A.: A history of graph entropy measures. Information Sciences 181, 57–78 (2011)
Anand, K., Bianconi, G., Severini, S.: Shannon and von Neumann entropy of random networks with heterogeneous expected degree. Physical Review E 83, 036109 (2011)
Scott, G.L., Longuett-Higgins, H.C.: An algorithm fro associating the features of two images. Proc. the Royal Society of London B 244, 313–320 (1991)
Xiao, B., Hancock, E.R., Wilson, R.C.: A generative model for graph matching and embedding. Computer Vision and Image Understanding 113(7), 777–789 (2009)
Munkres, J.: Algorithms for the assignment and transportation Problems. Journal of the Society for Industrial and Applied Mathematics 5(1), 32–38 (1957)
Borgwardts, K.M.: Graph Kernels. PhD thesis, Munchen (2007)
Biasotti, S., Marini, S., Mortara, M., Patané, G., Spagnuolo, M., Falcidieno, B.: 3D shape matching through topological structures. In: Nyström, I., Sanniti di Baja, G., Svensson, S. (eds.) DGCI 2003. LNCS, vol. 2886, pp. 194–203. Springer, Heidelberg (2003)
Bai, L., Hancock, E.R.: Graph kernels from the Jensen-Shannon divergence. Journal of Mathematical Imaging and Vision 47(1-2), 60–69 (2013)
Han, L., Escolano, F., Hancock, E.R., Wilson, R.C.: Graph characterizations from von Neumann entropy. Pattern Recognition Letters 33(15), 1958–1967 (2012)
Chang, C.-C., Lin, C.-J.: LIBSVM: A library for support vector machines (2011), Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bai, L., Ren, P., Bai, X., Hancock, E.R. (2014). A Graph Kernel from the Depth-Based Representation. In: Fränti, P., Brown, G., Loog, M., Escolano, F., Pelillo, M. (eds) Structural, Syntactic, and Statistical Pattern Recognition. S+SSPR 2014. Lecture Notes in Computer Science, vol 8621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44415-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-662-44415-3_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44414-6
Online ISBN: 978-3-662-44415-3
eBook Packages: Computer ScienceComputer Science (R0)