A Survey on Graph Kernels

2019-03-28 · Nils M. Kriege, Fredrik D. Johansson, Christopher Morris

Graph kernels have become an established and widely-used technique for solving classification tasks on graphs. This survey gives a comprehensive overview of techniques for kernel-based graph classification developed in the past 15 years. We describe and categorize graph kernels based on properties inherent to their design, such as the nature of their extracted graph features, their method of computation and their applicability to problems in practice. In an extensive experimental evaluation, we study the classification accuracy of a large suite of graph kernels on established benchmarks as well as new datasets. We compare the performance of popular kernels with several baseline methods and study the effect of applying a Gaussian RBF kernel to the metric induced by a graph kernel. In doing so, we find that simple baselines become competitive after this transformation on some datasets. Moreover, we study the extent to which existing graph kernels agree in their predictions (and prediction errors) and obtain a data-driven categorization of kernels as result. Finally, based on our experimental results, we derive a practitioner's guide to kernel-based graph classification.

📄 PDF Abstract BibTeX arXiv:1903.11835

Code (0)

등록된 구현이 없습니다.

Tasks

Classification General Classification Graph ClassificationSurvey

Graph Kernels: A Survey

2019-04-27 · Giannis Nikolentzos, Giannis Siglidis, Michalis Vazirgiannis

Graph kernels have attracted a lot of attention during the last decade, and have evolved into a rapidly developing branch of learning on structured data. During the past 20 years, the considerable research activity that …

Graph Classification Survey

Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nyström Method, and Use of Kernels in Machine Learning: Tutorial and Survey

2021-06-15 · Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, Mark Crowley

This is a tutorial and survey paper on kernels, kernel methods, and related fields. We start with reviewing the history of kernels in functional analysis and machine learning. Then, Mercer kernel, Hilbert and Banach spac…

BIG-bench Machine Learning Dimensionality Reduction Low-Rank Matrix Completion

Interpreting and Unifying Graph Neural Networks with An Optimization Framework

2021-01-28 · Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji 외

Graph Neural Networks (GNNs) have received considerable attention on graph-structured data learning for a wide variety of tasks. The well-designed propagation mechanism which has been demonstrated effective is the most f…

Deep Graph Kernels

2015-08-10 · KDD '15 Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2015 8 · Pinar Yanardag, S. V. N. Vishwanathan

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 Classification Language Modeling Language Modelling

Subgraph Matching Kernels for Attributed Graphs

2012-06-27 · Nils Kriege, Petra Mutzel

We propose graph kernels based on subgraph matchings, i.e. structure-preserving bijections between subgraphs. While recently proposed kernels based on common subgraphs (Wale et al., 2008; Shervashidze et al., 2009) in ge…

General Classification