Header logo is

Efficient Graphlet Kernels for Large Graph Comparison

2009

Conference Paper

ei


State-of-the-art graph kernels do not scale to large graphs with hundreds of nodes and thousands of edges. In this article we propose to compare graphs by counting {it graphlets}, ie subgraphs with $k$ nodes where $k in { 3, 4, 5 }$. Exhaustive enumeration of all graphlets being prohibitively expensive, we introduce two theoretically grounded speedup schemes, one based on sampling and the second one specifically designed for bounded degree graphs. In our experimental evaluation, our novel kernels allow us to efficiently compare large graphs that cannot be tackled by existing graph kernels.

Author(s): Shervashidze, N. and Vishwanathan, SVN. and Petri, TH. and Mehlhorn, K. and Borgwardt, KM.
Book Title: JMLR Workshop and Conference Proceedings Volume 5: AISTATS 2009
Journal: Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009)
Pages: 488-495
Year: 2009
Month: April
Day: 0
Editors: Van Dyk, D. , M. Welling
Publisher: MIT Press

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: Twelfth International Conference on Artificial Intelligence and Statistics
Event Place: Clearwater Beach, FL, USA

Address: Cambridge, MA, USA
Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{5664,
  title = {Efficient Graphlet Kernels for Large Graph Comparison},
  author = {Shervashidze, N. and Vishwanathan, SVN. and Petri, TH. and Mehlhorn, K. and Borgwardt, KM.},
  journal = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009)},
  booktitle = {JMLR Workshop and Conference Proceedings Volume 5: AISTATS 2009},
  pages = {488-495},
  editors = {Van Dyk, D. , M. Welling},
  publisher = {MIT Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Cambridge, MA, USA},
  month = apr,
  year = {2009},
  month_numeric = {4}
}