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

Keywords

  • Attributed graphs
  • Entropy
  • Local-global graph kernels

Fingerprint Dive into the research topics of 'A mixed entropy local-global reproducing kernel for attributed graphs'. Together they form a unique fingerprint.

  • 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