Graph Invariant Kernels
We introduce a novel kernel that upgrades the Weisfeiler-Lehman and other graph kernels to effectively exploit high-dimensional and continuous vertex attributes. Graphs are first decomposed into subgraphs. Vertices of the subgraphs are then compared by a kernel that combines the similarity of their labels and the similarity of their structural role, using a suitable vertex invariant. By changing this invariant we obtain a family of graph kernels which includes generalizations of Weisfeiler-Lehman, NSPDK, and propagation kernels. We demonstrate empirically that these kernels obtain state-of-the-art results on relational data sets.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph ClassificationSimilar Papers 제목 키워드 기반
HAQJSK: Hierarchical-Aligned Quantum Jensen-Shannon Kernels for Graph Classification
In this work, we propose a family of novel quantum kernels, namely the Hierarchical Aligned Quantum Jensen-Shannon Kernels (HAQJSK), for un-attributed graphs. Different from most existing classical graph kernels, the pro…
Graph ClassificationA Unifying View of Explicit and Implicit Feature Maps of Graph Kernels
Non-linear kernel methods can be approximated by fast linear ones using suitable explicit feature maps allowing their application to large scale problems. We investigate how convolution kernels for structured data are co…
DiversityGraph Kernels via Functional Embedding
We propose a representation of graph as a functional object derived from the power iteration of the underlying adjacency matrix. The proposed functional representation is a graph invariant, i.e., the functional remains u…
General ClassificationGraph ClassificationShift-invariant spaces, bandlimited spaces and reproducing kernel spaces with shift-invariant kernels on undirected finite graphs
In this paper, we introduce the concept of graph shift-invariant space (GSIS) on an undirected finite graph, which is the linear space of graph signals being invariant under graph shifts, and we study its bandlimiting, k…
Orthonormal Expansions for Translation-Invariant Kernels
We present a general Fourier analytic technique for constructing orthonormal basis expansions of translation-invariant kernels from orthonormal bases of $\mathscr{L}_2(\mathbb{R})$. This allows us to derive explicit expa…
Translation