Scalable kernels for graphs with continuous attributes

Aasa Feragen; Niklas Kasenburg; Jens Petersen; Marleen de Bruijne; Karsten Borgwardt

Scalable kernels for graphs with continuous attributes

Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, Karsten Borgwardt

Department of Computer Science

73 Citations (Scopus)

32 Downloads (Pure)

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(n⁴), where n is the number of nodes. In this paper, we present a class of graph kernels with computational complexity O(n ²(m+log n+δ² +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.

Original language	English
Title of host publication	27th Annual Conference on Neural Information Processing Systems 2013 : NIPS 2013
Editors	C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, K. Q. Weinberger
Number of pages	9
Publisher	Curran Associates, Inc.
Publication date	2013
Pages	216-224
ISBN (Print)	9781632660244
Publication status	Published - 2013
Event	27th Annual Conference on Neural Information Processing Systems - Lake Tahoe, United States Duration: 5 Dec 2013 → 10 Dec 2013 Conference number: 27

Conference

Conference	27th Annual Conference on Neural Information Processing Systems
Number	27
Country/Territory	United States
City	Lake Tahoe
Period	05/12/2013 → 10/12/2013

Series	Advances in Neural Information Processing Systems
Volume	26
ISSN	1049-5258

Access to Document

feragen_nips_2013Accepted author manuscript, 411 KB
Scalable kernels for graphs with continuous attributesFinal published version, 419 KB

http://papers.nips.cc/paper/5155-scalable-kernels-for-graphs-with-continuous-attributes

Cite this

Feragen, A., Kasenburg, N., Petersen, J., de Bruijne, M., & Borgwardt, K. (2013). Scalable kernels for graphs with continuous attributes. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, & K. Q. Weinberger (Eds.), 27th Annual Conference on Neural Information Processing Systems 2013: NIPS 2013 (pp. 216-224). Curran Associates, Inc.. http://papers.nips.cc/paper/5155-scalable-kernels-for-graphs-with-continuous-attributes

Scalable kernels for graphs with continuous attributes. / Feragen, Aasa; Kasenburg, Niklas; Petersen, Jens et al.
27th Annual Conference on Neural Information Processing Systems 2013: NIPS 2013. ed. / C. J. C. Burges; L. Bottou; M. Welling; Z. Ghahramani; K. Q. Weinberger. Curran Associates, Inc., 2013. p. 216-224 (Advances in Neural Information Processing Systems, Vol. 26).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Feragen, A, Kasenburg, N, Petersen, J , de Bruijne, M & Borgwardt, K 2013, Scalable kernels for graphs with continuous attributes. in CJC Burges, L Bottou, M Welling, Z Ghahramani & KQ Weinberger (eds), 27th Annual Conference on Neural Information Processing Systems 2013: NIPS 2013. Curran Associates, Inc., Advances in Neural Information Processing Systems, vol. 26, pp. 216-224, 27th Annual Conference on Neural Information Processing Systems, Lake Tahoe, United States, 05/12/2013. <http://papers.nips.cc/paper/5155-scalable-kernels-for-graphs-with-continuous-attributes>

Feragen A, Kasenburg N, Petersen J , de Bruijne M, Borgwardt K. Scalable kernels for graphs with continuous attributes. In Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, editors, 27th Annual Conference on Neural Information Processing Systems 2013: NIPS 2013. Curran Associates, Inc. 2013. p. 216-224. (Advances in Neural Information Processing Systems, Vol. 26).

Feragen, Aasa ; Kasenburg, Niklas ; Petersen, Jens et al. / Scalable kernels for graphs with continuous attributes. 27th Annual Conference on Neural Information Processing Systems 2013: NIPS 2013. editor / C. J. C. Burges ; L. Bottou ; M. Welling ; Z. Ghahramani ; K. Q. Weinberger. Curran Associates, Inc., 2013. pp. 216-224 (Advances in Neural Information Processing Systems, Vol. 26).

@inproceedings{9654686142b74e50b98777f668a3b5db,

title = "Scalable kernels for graphs with continuous attributes",

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(n 2(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.",

author = "Aasa Feragen and Niklas Kasenburg and Jens Petersen and {de Bruijne}, Marleen and Karsten Borgwardt",

year = "2013",

language = "English",

isbn = "9781632660244",

series = "Advances in Neural Information Processing Systems",

publisher = "Curran Associates, Inc.",

pages = "216--224",

editor = "Burges, {C. J. C.} and L. Bottou and M. Welling and Z. Ghahramani and Weinberger, {K. Q.}",

booktitle = "27th Annual Conference on Neural Information Processing Systems 2013",

note = "27th Annual Conference on Neural Information Processing Systems ; Conference date: 05-12-2013 Through 10-12-2013",

}

TY - GEN

T1 - Scalable kernels for graphs with continuous attributes

AU - Feragen, Aasa

AU - Kasenburg, Niklas

AU - Petersen, Jens

AU - de Bruijne, Marleen

AU - Borgwardt, Karsten

N1 - Conference code: 27

PY - 2013

Y1 - 2013

N2 - 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(n 2(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.

AB - 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(n 2(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.

M3 - Article in proceedings

SN - 9781632660244

T3 - Advances in Neural Information Processing Systems

SP - 216

EP - 224

BT - 27th Annual Conference on Neural Information Processing Systems 2013

A2 - Burges, C. J. C.

A2 - Bottou, L.

A2 - Welling, M.

A2 - Ghahramani, Z.

A2 - Weinberger, K. Q.

PB - Curran Associates, Inc.

T2 - 27th Annual Conference on Neural Information Processing Systems

Y2 - 5 December 2013 through 10 December 2013

ER -

Scalable kernels for graphs with continuous attributes

Abstract

Conference

Access to Document

Fingerprint

Cite this