A Deep Hybrid Graph Kernel Through Deep Learning Networks

Lixin Cui, Lu Bai, Luca Rossi, Yue Wang, Yuhang Jiao, Edwin R. Hancock

Research output: Contribution to journalConference article

Abstract

In this paper, we develop a new deep hybrid graph kernel. This is based on the depth-based matching kernel [1] and the Weisfeiler-Lehman subtree kernel [2], by jointly computing a basic deep kernel that simultaneously captures the relationship between the combined kernels through deep learning networks. Specifically, for a set of graphs under investigations, we commence by computing two kernel matrices using each of the separate kernels. With the two kernel matrices to hand, for each graph we use the kernel value between the graph and each of the training graphs as the graph characterisation vector. This vector can be seen as a kernel-based similarity embedding vector of the graph [3]. We use the embedding vectors of all graphs to train a deep auto encoder network, that is optimized using Stochastic Gradient Descent together with the Deep Belief Network for pretraining. The deep representation computed through the deep learning network captures the main relationship between the depth-based matching kernel and the Weisfeiler-Lehman subtree kernel. The resulting deep hybrid graph kernel is computed by summing the original kernels together with the dot product kernel between their deep representations. We show that the deep hybrid graph kernel not only captures the joint information between the associated depth-based matching and Weisfeiler-Lehman subtree kernels, but also reflects the information content over all graphs under investigations. Experimental evaluations demonstrate the effectiveness of the proposed kernel.
Original languageEnglish
Pages (from-to)1030-1035
Journal2018 24th International Conference on Pattern Recognition (ICPR)
DOIs
Publication statusPublished - 29 Nov 2018
Event2018 24th International Conference on Pattern Recognition (ICPR) - Beijing, China
Duration: 20 Aug 201824 Aug 2018

Fingerprint

Bayesian networks
Deep learning

Cite this

Cui, L., Bai, L., Rossi, L., Wang, Y., Jiao, Y., & Hancock, E. R. (2018). A Deep Hybrid Graph Kernel Through Deep Learning Networks. 2018 24th International Conference on Pattern Recognition (ICPR), 1030-1035. https://doi.org/10.1109/ICPR.2018.8546034
Cui, Lixin ; Bai, Lu ; Rossi, Luca ; Wang, Yue ; Jiao, Yuhang ; Hancock, Edwin R. / A Deep Hybrid Graph Kernel Through Deep Learning Networks. In: 2018 24th International Conference on Pattern Recognition (ICPR). 2018 ; pp. 1030-1035.
@article{5ede86fbc39d4552b2966cf3ce23dbe2,
title = "A Deep Hybrid Graph Kernel Through Deep Learning Networks",
abstract = "In this paper, we develop a new deep hybrid graph kernel. This is based on the depth-based matching kernel [1] and the Weisfeiler-Lehman subtree kernel [2], by jointly computing a basic deep kernel that simultaneously captures the relationship between the combined kernels through deep learning networks. Specifically, for a set of graphs under investigations, we commence by computing two kernel matrices using each of the separate kernels. With the two kernel matrices to hand, for each graph we use the kernel value between the graph and each of the training graphs as the graph characterisation vector. This vector can be seen as a kernel-based similarity embedding vector of the graph [3]. We use the embedding vectors of all graphs to train a deep auto encoder network, that is optimized using Stochastic Gradient Descent together with the Deep Belief Network for pretraining. The deep representation computed through the deep learning network captures the main relationship between the depth-based matching kernel and the Weisfeiler-Lehman subtree kernel. The resulting deep hybrid graph kernel is computed by summing the original kernels together with the dot product kernel between their deep representations. We show that the deep hybrid graph kernel not only captures the joint information between the associated depth-based matching and Weisfeiler-Lehman subtree kernels, but also reflects the information content over all graphs under investigations. Experimental evaluations demonstrate the effectiveness of the proposed kernel.",
author = "Lixin Cui and Lu Bai and Luca Rossi and Yue Wang and Yuhang Jiao and Hancock, {Edwin R.}",
year = "2018",
month = "11",
day = "29",
doi = "10.1109/ICPR.2018.8546034",
language = "English",
pages = "1030--1035",

}

Cui, L, Bai, L, Rossi, L, Wang, Y, Jiao, Y & Hancock, ER 2018, 'A Deep Hybrid Graph Kernel Through Deep Learning Networks', 2018 24th International Conference on Pattern Recognition (ICPR), pp. 1030-1035. https://doi.org/10.1109/ICPR.2018.8546034

A Deep Hybrid Graph Kernel Through Deep Learning Networks. / Cui, Lixin; Bai, Lu; Rossi, Luca; Wang, Yue; Jiao, Yuhang; Hancock, Edwin R.

In: 2018 24th International Conference on Pattern Recognition (ICPR), 29.11.2018, p. 1030-1035.

Research output: Contribution to journalConference article

TY - JOUR

T1 - A Deep Hybrid Graph Kernel Through Deep Learning Networks

AU - Cui, Lixin

AU - Bai, Lu

AU - Rossi, Luca

AU - Wang, Yue

AU - Jiao, Yuhang

AU - Hancock, Edwin R.

PY - 2018/11/29

Y1 - 2018/11/29

N2 - In this paper, we develop a new deep hybrid graph kernel. This is based on the depth-based matching kernel [1] and the Weisfeiler-Lehman subtree kernel [2], by jointly computing a basic deep kernel that simultaneously captures the relationship between the combined kernels through deep learning networks. Specifically, for a set of graphs under investigations, we commence by computing two kernel matrices using each of the separate kernels. With the two kernel matrices to hand, for each graph we use the kernel value between the graph and each of the training graphs as the graph characterisation vector. This vector can be seen as a kernel-based similarity embedding vector of the graph [3]. We use the embedding vectors of all graphs to train a deep auto encoder network, that is optimized using Stochastic Gradient Descent together with the Deep Belief Network for pretraining. The deep representation computed through the deep learning network captures the main relationship between the depth-based matching kernel and the Weisfeiler-Lehman subtree kernel. The resulting deep hybrid graph kernel is computed by summing the original kernels together with the dot product kernel between their deep representations. We show that the deep hybrid graph kernel not only captures the joint information between the associated depth-based matching and Weisfeiler-Lehman subtree kernels, but also reflects the information content over all graphs under investigations. Experimental evaluations demonstrate the effectiveness of the proposed kernel.

AB - In this paper, we develop a new deep hybrid graph kernel. This is based on the depth-based matching kernel [1] and the Weisfeiler-Lehman subtree kernel [2], by jointly computing a basic deep kernel that simultaneously captures the relationship between the combined kernels through deep learning networks. Specifically, for a set of graphs under investigations, we commence by computing two kernel matrices using each of the separate kernels. With the two kernel matrices to hand, for each graph we use the kernel value between the graph and each of the training graphs as the graph characterisation vector. This vector can be seen as a kernel-based similarity embedding vector of the graph [3]. We use the embedding vectors of all graphs to train a deep auto encoder network, that is optimized using Stochastic Gradient Descent together with the Deep Belief Network for pretraining. The deep representation computed through the deep learning network captures the main relationship between the depth-based matching kernel and the Weisfeiler-Lehman subtree kernel. The resulting deep hybrid graph kernel is computed by summing the original kernels together with the dot product kernel between their deep representations. We show that the deep hybrid graph kernel not only captures the joint information between the associated depth-based matching and Weisfeiler-Lehman subtree kernels, but also reflects the information content over all graphs under investigations. Experimental evaluations demonstrate the effectiveness of the proposed kernel.

UR - https://ieeexplore.ieee.org/document/8546034/

U2 - 10.1109/ICPR.2018.8546034

DO - 10.1109/ICPR.2018.8546034

M3 - Conference article

SP - 1030

EP - 1035

ER -

Cui L, Bai L, Rossi L, Wang Y, Jiao Y, Hancock ER. A Deep Hybrid Graph Kernel Through Deep Learning Networks. 2018 24th International Conference on Pattern Recognition (ICPR). 2018 Nov 29;1030-1035. https://doi.org/10.1109/ICPR.2018.8546034