Current graph kernels suffer from two limitations: graph kernels based on counting particular types of subgraphs ignore the relative position of these subgraphs to each other, while graph kernels based on algebraic methods are limited to graphs without node labels. In this paper we present the graphlet spectrum, a system of graph invariants derived by means of group representation theory that capture information about the number as well as the position of labeled subgraphs in a given graph. In our experimental evaluation the graphlet spectrum outperforms state-of-the-art graph kernels.

Author(s): Kondor, R. and Shervashidze, N. and Borgwardt, KM.
Journal: Proceedings of the 26th International Conference on Machine Learning (ICML 2009)
Pages: 529-536
Year: 2009
Month: June
Day: 0
Editors: Danyluk, A. , L. Bottou, M. Littman
Publisher: ACM Press
Bibtex Type: Conference Paper (inproceedings)
Address: New York, NY, USA
DOI: 10.1145/1553374.1553443
Event Name: 26th International Conference on Machine Learning (ICML 2009)
Event Place: Montreal, Canada
Digital: 0
Electronic Archiving: grant_archive
ISBN: 978-1-605-58516-1
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik
Links:

BibTex

@inproceedings{5913,
  title = {The graphlet spectrum},
  journal = {Proceedings of the 26th International Conference on Machine Learning (ICML 2009)},
  abstract = {Current graph kernels suffer from two limitations: graph kernels based on counting particular types of subgraphs ignore the relative position of these subgraphs to each other, while graph kernels based on algebraic methods are limited to graphs without node labels. In this paper we present the graphlet spectrum, a system of graph invariants derived by means of group representation theory that capture information about the number as well as the position of labeled subgraphs in a given graph. In our experimental evaluation the graphlet spectrum outperforms state-of-the-art graph kernels.},
  pages = {529-536},
  editors = {Danyluk, A. , L. Bottou, M. Littman},
  publisher = {ACM Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {New York, NY, USA},
  month = jun,
  year = {2009},
  slug = {5913},
  author = {Kondor, R. and Shervashidze, N. and Borgwardt, KM.},
  month_numeric = {6}
}