Efficient graphlet kernels for large graph comparison
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 ε {3; 4; 5g}. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph ClassificationSimilar Papers 제목 키워드 기반
Graph Kernels based on High Order Graphlet Parsing and Hashing
Graph-based methods are known to be successful in many machine learning and pattern classification tasks. These methods consider semi-structured data as graphs where nodes correspond to primitives (parts, interest points…
BIG-bench Machine LearningVocal Bursts Intensity PredictionThe Structurally Smoothed Graphlet Kernel
A commonly used paradigm for representing graphs is to use a vector that contains normalized frequencies of occurrence of certain motifs or sub-graphs. This vector representation can be used in a variety of applications,…
Graphlet-based lazy associative graph classification
The paper addresses the graph classification problem and introduces a modification of the lazy associative classification method to efficiently handle intersections of graphs. Graph intersections are approximated with al…
ClassificationGeneral ClassificationGraph ClassificationDeep Graph Kernels
In this paper, we present Deep Graph Kernels (DGK), a unified framework to learn latent representations of sub-structures for graphs, inspired by latest advancements in language modeling and deep learning. Our framework …
Graph ClassificationLanguage ModelingLanguage ModellingA Temporal Graphlet Kernel for Classifying Dissemination in Evolving Networks
We introduce the \emph{temporal graphlet kernel} for classifying dissemination processes in labeled temporal graphs. Such dissemination processes can be spreading (fake) news, infectious diseases, or computer viruses in …