zbMATH — the first resource for mathematics

Fast depth-based subgraph kernels for unattributed graphs. (English) Zbl 1394.68272
Summary: In this paper, we investigate two fast subgraph kernels based on a depth-based representation of graph-structure. Both methods gauge depth information through a family of \(K\)-layer expansion subgraphs rooted at a vertex [F. Escolano et al., “Heat diffusion: thermodynamic depth complexity of networks”, Phys. Rev. E 85, No. 3, 036206, 15 p. (2012; doi:10.1103/physreve.85.036206)]. The first method commences by computing a centroid-based complexity trace for each graph, using a depth-based representation rooted at the centroid vertex that has minimum shortest path length variance to the remaining vertices [the authors, Pattern Recognition 47, No. 3, 1172–1186 (2014; Zbl 1326.68241)]. This subgraph kernel is computed by measuring the Jensen-Shannon divergence between centroid-based complexity entropy traces. The second method, on the other hand, computes a depth-based representation around each vertex in turn. The corresponding subgraph kernel is computed using isomorphisms tests to compare the depth-based representation rooted at each vertex in turn. For graphs with \(n\) vertices, the time complexities for the two new kernels are \(O(n^2)\) and \(O(n^3)\), in contrast to \(O(n^6)\) for the classic Gärtner graph kernel [T. Gärtner et al., Lect. Notes Comput. Sci. 2777, 129–143 (2003; Zbl 1274.68312)]. Key to achieving this efficiency is that we compute the required Shannon entropy of the random walk for our kernels with \(O(n^2)\) operations. This computational strategy enables our subgraph kernels to easily scale up to graphs of reasonably large sizes and thus overcome the size limits arising in state-of-the-art graph kernels. Experiments on standard bioinformatics and computer vision graph datasets demonstrate the effectiveness and efficiency of our new subgraph kernels.

68T05 Learning and adaptive systems in artificial intelligence
68R10 Graph theory (including graph drawing) in computer science
68T45 Machine vision and scene understanding
94A17 Measures of information, entropy
Full Text: DOI
[1] Escolano, F.; Hancock, E. R.; Lozano, M. A., Heat diffusionthermodynamic depth complexity of networks, Phys. Rev. E, 85, 036206, (2012)
[2] Bai, L.; Hancock, Edwin R., Depth-based complexity traces of graphs, Pattern Recognit., 47, (2013), 17721186
[3] T. Gärtner, P.A. Flach, S. Wrobel, On graph kernels: hardness results and efficient alternatives, in: Proceedings of Conference on Learning Theory, 2003, pp. 129-143. · Zbl 1274.68312
[4] Bai, L.; Hancock, E. R., Graph kernels from the Jensen-Shannon divergence, J. Math. Imaging Vis., 47, 60-69, (2013) · Zbl 1276.68152
[5] Shervashidze, N.; Schweitzer, P.; Leeuwen, E. J.; Mehlhorn, K.; Borgwardt, K. M., Weisfeiler-lehman graph kernels, J. Mach. Learn. Res., 1, 1-48, (2010)
[6] Li, G.; Semerci, M.; Yener, B.; Zaki, M. J., Effective graph classification based on topological and label attributes, Stat. Anal. Data Min., 5, 265-283, (2012)
[7] H. Kashima, K. Tsuda, A. Inokuchi, Marginalized kernels between labeled graphs, in: Proceedings of International Conference on Machine Learning, 2003, pp. 321-328.
[8] K.M. Borgwardt, H. Kriegel, Shortest-path kernels on graphs, in: Proceedings of the IEEE International Conference on Data Mining, 2005, pp. 74-81.
[9] Aziz, F.; Wilson, R. C.; Hancock, E. R., Backtrackless walks on a graph, IEEE Trans. Neural Netw. Learn. Syst., 24, 977-989, (2013)
[10] Ren, P.; Wilson, R. C.; Hancock, E. R., Graph characterization via ihara coefficients, IEEE Trans. Neural Netw., 22, 233-245, (2011)
[11] F. Costa, K.D. Grave, Fast neighborhood subgraph pairwise distance kernel, in: Proceedings of International Conference on Machine Learning, 2010, 255-262.
[12] Z. Harchaoui, F. Bach, Image classification with segmentation graph kernels, in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2007.
[13] F.R. Bach, Graph kernels between point clouds, in: Proceedings of International Conference on Machine Learning, 2008, 25-32.
[14] N. Kriege, P. Mutzel, Subgraph matching kernels for attributed graphs, in: Proceedings of International Conference on Machine Learning, 2012.
[15] L. Bai, P. Ren, E.R. Hancock. A Hypergraph Kernel from Isomorphism Tests. In: proceedings of International Conference on Pattern Recognition, pp. 3880-3885, 2014
[16] Lamberti, P. W.; Majtey, A. P.; Borras, A.; Casas, M.; Plastino, A., Metric character of the quantum Jensen-Shannon divergence, Phys. Rev. A, 77, 052311, (2008)
[17] Crutchfield, J. P.; Shalizi, C. R., Thermodynamic depth of causal statesobjective complexity via minimal representations, Phys. Rev. E, 59, 275283, (1999)
[18] L. Bai, E.R. Hancock. L. Han, P. Ren, Graph clustering using graph entropy complexity traces, in: Proceedings of International Conference on Pattern Recognition, 2012, pp. 2881-2884.
[19] L. Bai, E.R. Hancock, Graph complexity from the Jensen-Shannon divergence, in: Proceedings of SSPR/SPR, 2012, pp. 79-98.
[20] L. Bai, E.R. Hancock, Graph clustering using the Jensen-Shannon kernel, in: Proceedings of International Conference on Computer Analysis of Images and Patterns, 2011, pp. 394-401.
[21] Dehmer, M., Information-theoretic concepts for the analysis of complex networks, Appl. Artif. Intell., 22, 684-706, (2008)
[22] Anand, K.; Bianconi, G.; Severini, S., Shannon and von Neumann entropy of random networks with heterogeneous expected degree, Phys. Rev. E, 83, 036169, (2011)
[23] Passerini, F.; Severini, S., Quantifying complexity in networksthe von Neumann entropy, Int. J. Agent Technol. Syst., 1, 58-67, (2009)
[24] Gadouleau, M.; Riis, S., Graph-theoretical constructions for graph entropy and network coding based communications, IEEE Trans. Inf. Theory, 57, 6703-6717, (2011) · Zbl 1365.94557
[25] J. Köner, Coding of an information source having ambiguous alphabet and the entropy of graphs, in: Proceedings of the 6th Prague Conference on Information Theory, Statistical Decision Function, Random Processes, 1971, pp. 411-425.
[26] Riesen, K.; Bunke, H., Graph Classification and Clustering based on Vector Space Embedding, (2010), World Scientific Publishing Co., Inc. · Zbl 1231.68233
[27] S. Biasotti, S. Marini, M. Mortara, G. Patanè, M. Spagnuolo, B. Falcidieno, 3D shape matching through topological structures, in: Proceedings of DGCI, 2003, pp. 194-203. · Zbl 1254.68237
[28] Shervashidze, N.; Vishwanathan, S. V.N.; Petri, T.; Mehlhorn, K.; Borgwardt, K. M., Efficient graphlet kernels for large graph comparison, J. Mach. Learn. Res., 5, 488-495, (2009)
[29] Emms, D.; Wilson, R. C.; Hancock, E. R., Graph matching using the interference of continuous-time quantum walks, Pattern Recognit., 42, 985-1002, (2009) · Zbl 1181.68232
[30] Ren, P.; Aleksic, T.; Emms, D.; Wilson, R. C.; Hancock, E. R., Quantum walks, ihara zeta functions and cospectrality in regular graphs, Quant. Inf. Process., 10, 405-417, (2011) · Zbl 1216.81043
[31] Debnath, A. K.; Lopez de Compadre, R. L.; Debnath, G.; Shusterman, A. J.; Hansch, C., Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds, correlation with molecular orbital energies and hydrophobicity, J. Med. Chem., 34, 786-797, (1991)
[32] Borgwardt, K. M.; Ong, C. S.; Schoenauer, S.; Vishwanathan, S. V.N.; Smola, A. J.; Kriegel, H. P., Protein function prediction via graph kernels, Bioinformatics, 21, Supplement 1, 47-56, (2005)
[33] Dobson, P. D.; Doig, A. J., Distinguishing enzyme structures from non-enzymes without alignments, J. Mol. Biol., 330, 771-783, (2003)
[34] N. Wale, G. Karypis, Comparison of descriptor spaces for chemical compound retrieval and classification, in: Proceedings of IEEE International Conference on Data Mining, 2006, pp. 678-689.
[35] Schomburg, I.; Chang, A.; Ebeling, C.; Gremse, M.; Heldt, C.; Huhn, G.; Schomburg, D., The enzyme databaseupdates and major new developments, Nucl. Acids Res., 32, 431-433, (2004)
[36] Bai, L.; Rossi, L.; Torsello, A.; Hancock, E. R., A quantum Jensen-Shannon graph kernel for unattributed graphs, Pattern Recognit., 48, 344-355, (2015) · Zbl 1373.68345
[37] L. Bai, L. Rossi, H. Bunke, E.R. Hancock, Attributed graph kernels using the Jensen-Tsallis q-differences, in: Proceedings of Eurepean Conference on Machine Learning and Knowledge Discovery in Databases(ECML-PKDD), 2014, Part I, pp. 15-19.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.