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

Datalogisk Institut

73 Citationer (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.

Originalsprog	Engelsk
Titel	27th Annual Conference on Neural Information Processing Systems 2013 : NIPS 2013
Redaktører	C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, K. Q. Weinberger
Antal sider	9
Forlag	Curran Associates, Inc.
Publikationsdato	2013
Sider	216-224
ISBN (Trykt)	9781632660244
Status	Udgivet - 2013
Begivenhed	27th Annual Conference on Neural Information Processing Systems - Lake Tahoe, USA Varighed: 5 dec. 2013 → 10 dec. 2013 Konferencens nummer: 27

Konference

Konference	27th Annual Conference on Neural Information Processing Systems
Nummer	27
Land/Område	USA
By	Lake Tahoe
Periode	05/12/2013 → 10/12/2013

Navn	Advances in Neural Information Processing Systems
Vol/bind	26
ISSN	1049-5258

Adgang til dokumentet

feragen_nips_2013Accepteret manuskript, 411 KB
Scalable kernels for graphs with continuous attributesForlagets udgivne version, 419 KB

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

Citationsformater

Feragen, A., Kasenburg, N., Petersen, J., de Bruijne, M., & Borgwardt, K. (2013). Scalable kernels for graphs with continuous attributes. I C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, & K. Q. Weinberger (red.), 27th Annual Conference on Neural Information Processing Systems 2013: NIPS 2013 (s. 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. red. / C. J. C. Burges; L. Bottou; M. Welling; Z. Ghahramani; K. Q. Weinberger. Curran Associates, Inc., 2013. s. 216-224 (Advances in Neural Information Processing Systems, Bind 26).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Feragen, A, Kasenburg, N, Petersen, J , de Bruijne, M & Borgwardt, K 2013, Scalable kernels for graphs with continuous attributes. i CJC Burges, L Bottou, M Welling, Z Ghahramani & KQ Weinberger (red), 27th Annual Conference on Neural Information Processing Systems 2013: NIPS 2013. Curran Associates, Inc., Advances in Neural Information Processing Systems, bind 26, s. 216-224, 27th Annual Conference on Neural Information Processing Systems, Lake Tahoe, USA, 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. I Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, red., 27th Annual Conference on Neural Information Processing Systems 2013: NIPS 2013. Curran Associates, Inc. 2013. s. 216-224. (Advances in Neural Information Processing Systems, Bind 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. red. / C. J. C. Burges ; L. Bottou ; M. Welling ; Z. Ghahramani ; K. Q. Weinberger. Curran Associates, Inc., 2013. s. 216-224 (Advances in Neural Information Processing Systems, Bind 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater