A mixed entropy local-global reproducing kernel for attributed graphs

Lixin Cui, Lu Bai*, Luca Rossi, Zhihong Zhang, Lixiang Xu, Edwin R. Hancock

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we develop a new mixed entropy local-global reproducing kernel for vertex attributed graphs based on depth-based representations that naturally reflect both local and global entropy based graph characteristics. Specifically, for a pair of graphs, we commence by computing the nest depth-based representations rooted at the centroid vertices. The resulting mixed local-global reproducing kernel for a pair of graphs is computed by measuring a basic H1-reproducing kernel between their nest representations associated with different entropy measures. We show that the proposed kernel not only reflect both the local and global graph characteristics through the nest depth-based representations, but also reflect rich edge connection information and vertex label information through different kinds of entropy measures. Moreover, since both the required basic H1-reproducing kernel and the nest depth-based representation can be computed in a polynomial time, the new proposed kernel processes efficient computational complexity. Experiments on standard graph datasets demonstrate the effectiveness and efficiency of the proposed kernel.

Original languageEnglish
Title of host publicationStructural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings
PublisherSpringer
Pages501-511
Number of pages11
ISBN (Print)9783319977843
DOIs
Publication statusPublished - 2 Aug 2018
EventJoint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2018 and Statistical Techniques in Pattern Recognition, SPR 2018 - Beijing, China
Duration: 17 Aug 201819 Aug 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11004 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceJoint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2018 and Statistical Techniques in Pattern Recognition, SPR 2018
CountryChina
CityBeijing
Period17/08/1819/08/18

Fingerprint

Reproducing Kernel
Entropy
Nest
Graph in graph theory
kernel
Labels
Computational complexity
Polynomials
Vertex of a graph
Centroid
Polynomial time
Computational Complexity
Computing
Experiments
Demonstrate
Experiment

Keywords

  • Attributed graphs
  • Entropy
  • Local-global graph kernels

Cite this

Cui, L., Bai, L., Rossi, L., Zhang, Z., Xu, L., & Hancock, E. R. (2018). A mixed entropy local-global reproducing kernel for attributed graphs. In Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings (pp. 501-511). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11004 LNCS). Springer. https://doi.org/10.1007/978-3-319-97785-0_48
Cui, Lixin ; Bai, Lu ; Rossi, Luca ; Zhang, Zhihong ; Xu, Lixiang ; Hancock, Edwin R. / A mixed entropy local-global reproducing kernel for attributed graphs. Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings. Springer, 2018. pp. 501-511 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{616f4753525642a293a9fdec3ddf32bc,
title = "A mixed entropy local-global reproducing kernel for attributed graphs",
abstract = "In this paper, we develop a new mixed entropy local-global reproducing kernel for vertex attributed graphs based on depth-based representations that naturally reflect both local and global entropy based graph characteristics. Specifically, for a pair of graphs, we commence by computing the nest depth-based representations rooted at the centroid vertices. The resulting mixed local-global reproducing kernel for a pair of graphs is computed by measuring a basic H1-reproducing kernel between their nest representations associated with different entropy measures. We show that the proposed kernel not only reflect both the local and global graph characteristics through the nest depth-based representations, but also reflect rich edge connection information and vertex label information through different kinds of entropy measures. Moreover, since both the required basic H1-reproducing kernel and the nest depth-based representation can be computed in a polynomial time, the new proposed kernel processes efficient computational complexity. Experiments on standard graph datasets demonstrate the effectiveness and efficiency of the proposed kernel.",
keywords = "Attributed graphs, Entropy, Local-global graph kernels",
author = "Lixin Cui and Lu Bai and Luca Rossi and Zhihong Zhang and Lixiang Xu and Hancock, {Edwin R.}",
year = "2018",
month = "8",
day = "2",
doi = "10.1007/978-3-319-97785-0_48",
language = "English",
isbn = "9783319977843",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "501--511",
booktitle = "Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings",
address = "Germany",

}

Cui, L, Bai, L, Rossi, L, Zhang, Z, Xu, L & Hancock, ER 2018, A mixed entropy local-global reproducing kernel for attributed graphs. in Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11004 LNCS, Springer, pp. 501-511, Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2018 and Statistical Techniques in Pattern Recognition, SPR 2018, Beijing, China, 17/08/18. https://doi.org/10.1007/978-3-319-97785-0_48

A mixed entropy local-global reproducing kernel for attributed graphs. / Cui, Lixin; Bai, Lu; Rossi, Luca; Zhang, Zhihong; Xu, Lixiang; Hancock, Edwin R.

Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings. Springer, 2018. p. 501-511 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11004 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - A mixed entropy local-global reproducing kernel for attributed graphs

AU - Cui, Lixin

AU - Bai, Lu

AU - Rossi, Luca

AU - Zhang, Zhihong

AU - Xu, Lixiang

AU - Hancock, Edwin R.

PY - 2018/8/2

Y1 - 2018/8/2

N2 - In this paper, we develop a new mixed entropy local-global reproducing kernel for vertex attributed graphs based on depth-based representations that naturally reflect both local and global entropy based graph characteristics. Specifically, for a pair of graphs, we commence by computing the nest depth-based representations rooted at the centroid vertices. The resulting mixed local-global reproducing kernel for a pair of graphs is computed by measuring a basic H1-reproducing kernel between their nest representations associated with different entropy measures. We show that the proposed kernel not only reflect both the local and global graph characteristics through the nest depth-based representations, but also reflect rich edge connection information and vertex label information through different kinds of entropy measures. Moreover, since both the required basic H1-reproducing kernel and the nest depth-based representation can be computed in a polynomial time, the new proposed kernel processes efficient computational complexity. Experiments on standard graph datasets demonstrate the effectiveness and efficiency of the proposed kernel.

AB - In this paper, we develop a new mixed entropy local-global reproducing kernel for vertex attributed graphs based on depth-based representations that naturally reflect both local and global entropy based graph characteristics. Specifically, for a pair of graphs, we commence by computing the nest depth-based representations rooted at the centroid vertices. The resulting mixed local-global reproducing kernel for a pair of graphs is computed by measuring a basic H1-reproducing kernel between their nest representations associated with different entropy measures. We show that the proposed kernel not only reflect both the local and global graph characteristics through the nest depth-based representations, but also reflect rich edge connection information and vertex label information through different kinds of entropy measures. Moreover, since both the required basic H1-reproducing kernel and the nest depth-based representation can be computed in a polynomial time, the new proposed kernel processes efficient computational complexity. Experiments on standard graph datasets demonstrate the effectiveness and efficiency of the proposed kernel.

KW - Attributed graphs

KW - Entropy

KW - Local-global graph kernels

UR - http://www.scopus.com/inward/record.url?scp=85052211769&partnerID=8YFLogxK

UR - https://link.springer.com/chapter/10.1007%2F978-3-319-97785-0_48

U2 - 10.1007/978-3-319-97785-0_48

DO - 10.1007/978-3-319-97785-0_48

M3 - Conference contribution

AN - SCOPUS:85052211769

SN - 9783319977843

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 501

EP - 511

BT - Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings

PB - Springer

ER -

Cui L, Bai L, Rossi L, Zhang Z, Xu L, Hancock ER. A mixed entropy local-global reproducing kernel for attributed graphs. In Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings. Springer. 2018. p. 501-511. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-97785-0_48