Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für biologische Kybernetik     Collection: Biologische Kybernetik     Display Documents



ID: 461818.0, MPI für biologische Kybernetik / Biologische Kybernetik
Efficient Graphlet Kernels for Large Graph Comparison
Authors:Shervashidze, N.; Vishwanathan, S.V.N.; Petri, T.H.; Mehlhorn, K.; Borgwardt, K.M.
Editors:Dyk, D. Van; Welling, M.
Date of Publication (YYYY-MM-DD):2009-04
Title of Proceedings:Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics (AIStats 2009)
Start Page:488
End Page:495
Physical Description:8
Audience:Not Specified
Intended Educational Use:No
Abstract / Description: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.
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Holger Fischer
Affiliations:MPI für biologische Kybernetik/Empirical Inference (Dept. Schölkopf)
Identifiers:LOCALID:5664
URL:http://www.ics.uci.edu/~aistats/index.html
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.