nips nips2013 nips2013-289 nips2013-289-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, Karsten Borgwardt
Abstract: While graphs with continuous node attributes arise in many applications, stateof-the-art graph kernels for comparing continuous-attributed graphs suffer from a high runtime complexity. For instance, the popular shortest path kernel scales as O(n4 ), where n is the number of nodes. In this paper, we present a class of graph kernels with computational complexity O(n2 (m + log n + δ 2 + d)), where δ is the graph diameter, m is the number of edges, and d is the dimension of the node attributes. Due to the sparsity and small diameter of real-world graphs, these kernels typically scale comfortably to large graphs. In our experiments, the presented kernels outperform state-of-the-art kernels in terms of speed and accuracy on classification benchmark datasets. 1
[1] N. Shervashidze, S.V.N. Vishwanathan, T. Petri, K. Mehlhorn, and K.M. Borgwardt. Efficient graphlet kernels for large graph comparison. JMLR, 5:488–495, 2009.
[2] N. Shervashidze, P. Schweitzer, E.J. van Leeuwen, K. Mehlhorn, and K.M. Borgwardt. WeisfeilerLehman graph kernels. JMLR, 12:2539–2561, 2011.
[3] D. Haussler. Convolution kernels on discrete structures. Technical report, Department of Computer Science, University of California at Santa Cruz, 1999.
[4] M. Collins and N. Duffy. Convolution kernels for natural language. In NIPS, pages 625–632, 2001.
[5] S.V.N. Vishwanathan and A.J. Smola. Fast kernels for string and tree matching. In NIPS, pages 569–576, 2002.
[6] C. Cortes, P. Haffner, and M. Mohri. Rational kernels: Theory and algorithms. JMLR, 5:1035–1062, 2004.
[7] D. Kimura and H. Kashima. Fast computation of subpath kernel for trees. In ICML, 2012.
[8] P. Mah´ and J.-P. Vert. Graph kernels based on tree patterns for molecules. Machine Learning, 75:3–35, e 2009.
[9] H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In ICML, pages 321–328, 2003.
[10] T. G¨ rtner, P. Flach, and S. Wrobel. On graph kernels: Hardness results and efficient alternatives. In a Learning Theory and Kernel Machines, volume 2777 of LNCS, pages 129–143, 2003.
[11] S.V.N. Vishwanathan, N.N. Schraudolph, R.I. Kondor, and K.M. Borgwardt. Graph kernels. JMLR, 11:1201–1242, 2010.
[12] F.R. Bach. Graph kernels between point clouds. In ICML, pages 25–32, 2008.
[13] P. Mah´ , N. Ueda, T. Akutsu, J.-L. Perret, and J.-P. Vert. Extensions of marginalized graph kernels. In e ICML, 2004.
[14] N. Kriege and P. Mutzel. Subgraph matching kernels for attributed graphs. In ICML, 2012.
[15] B. Ga¨ z` re, L. Brun, and D. Villemin. Two new graphs kernels in chemoinformatics. Pattern Recognition u e Letters, 15:2038–2047, 2012.
[16] M. Neumann, N. Patricia, R. Garnett, and K. Kersting. Efficient graph kernels by randomization. In ECML/PKDD (1), pages 378–393, 2012.
[17] K.M. Borgwardt and H.-P. Kriegel. Shortest-path kernels on graphs. ICDM, 2005.
[18] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009.
[19] A. Feragen, J. Petersen, D. Grimm, A. Dirksen, J.H. Pedersen, K. Borgwardt, and M. de Bruijne. Geometric tree kernels: Classification of COPD from airway tree geometry. In IPMI 2013, 2013.
[20] N. Shervashidze. Graph kernels code, http://mlcb.is.tuebingen.mpg.de/Mitarbeiter/ Nino/Graphkernels/.
[21] D. Gleich. MatlabBGL http://dgleich.github.io/matlab-bgl/.
[22] I. Schomburg, A. Chang, C. Ebeling, M. Gremse, C. Heldt, G. Huhn, and D. Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic Acids Research, 32:431–433, 2004.
[23] P.D. Dobson and A.J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 330(4):771 – 783, 2003.
[24] K.M. Borgwardt, C.S. Ong, S. Sch¨ nauer, S.V.N. Vishwanathan, A.J. Smola, and H.-P. Kriegel. Protein o function prediction via graph kernels. Bioinformatics, 21(suppl 1):i47–i56, 2005.
[25] J. Pedersen, H. Ashraf, A. Dirksen, K. Bach, H. Hansen, P. Toennesen, H. Thorsen, J. Brodersen, B. Skov, M. Døssing, J. Mortensen, K. Richter, P. Clementsen, and N. Seersholm. The Danish randomized lung cancer CT screening trial - overall design and results of the prevalence round. J Thorac Oncol, 4(5):608– 614, May 2009.
[26] J. Petersen, M. Nielsen, P. Lo, Z. Saghir, A. Dirksen, and M. de Bruijne. Optimal graph based segmentation using flow lines with application to airway wall segmentation. In IPMI, LNCS, pages 49–60, 2011.
[27] C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Trans. Int. Syst. and Tech., 2:27:1–27:27, 2011. Software available at http://www.csie.ntu.edu.tw/˜cjlin/ libsvm. 9