Efficient graphlet kernels for large graph comparison

Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, Karsten Borgwardt
Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, PMLR 5:488-495, 2009.

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 $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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v5-shervashidze09a, title = {Efficient graphlet kernels for large graph comparison}, author = {Shervashidze, Nino and Vishwanathan, SVN and Petri, Tobias and Mehlhorn, Kurt and Borgwardt, Karsten}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {488--495}, year = {2009}, editor = {van Dyk, David and Welling, Max}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/shervashidze09a/shervashidze09a.pdf}, url = {https://proceedings.mlr.press/v5/shervashidze09a.html}, 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 $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.} }
Endnote
%0 Conference Paper %T Efficient graphlet kernels for large graph comparison %A Nino Shervashidze %A SVN Vishwanathan %A Tobias Petri %A Kurt Mehlhorn %A Karsten Borgwardt %B Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-shervashidze09a %I PMLR %P 488--495 %U https://proceedings.mlr.press/v5/shervashidze09a.html %V 5 %X 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 $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.
RIS
TY - CPAPER TI - Efficient graphlet kernels for large graph comparison AU - Nino Shervashidze AU - SVN Vishwanathan AU - Tobias Petri AU - Kurt Mehlhorn AU - Karsten Borgwardt BT - Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-shervashidze09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 488 EP - 495 L1 - http://proceedings.mlr.press/v5/shervashidze09a/shervashidze09a.pdf UR - https://proceedings.mlr.press/v5/shervashidze09a.html AB - 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 $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. ER -
APA
Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K. & Borgwardt, K.. (2009). Efficient graphlet kernels for large graph comparison. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:488-495 Available from https://proceedings.mlr.press/v5/shervashidze09a.html.

Related Material