English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Efficient graphlet kernels for large graph comparison

MPS-Authors
/persons/resource/persons75313

Borgwardt,  Karsten       
Dept. Empirical Inference, Max Planck Institute for Intelligent System, Max Planck Society;

Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Shervashidze, N., Vishwanathan, S. V. N., Petri, T., Mehlhorn, K., & Borgwardt, K. (2009). Efficient graphlet kernels for large graph comparison. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5, 488-495.


Cite as: https://hdl.handle.net/21.11116/0000-000C-F394-A
Abstract
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 graphlets, i.e., subgraphs with kkk nodes where k∈{3,4,5}k∈{3,4,5}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.