A mixed entropy local-global reproducing kernel for attributed graphs

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

doi:10.1007/978-3-319-97785-0_48

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/Published conference output › Conference publication

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 H¹-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 H¹-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 language	English
Title of host publication	Structural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, S+SSPR 2018, Proceedings
Publisher	Springer
Pages	501-511
Number of pages	11
ISBN (Print)	9783319977843
DOIs	https://doi.org/10.1007/978-3-319-97785-0_48
Publication status	Published - 2 Aug 2018
Event	Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2018 and Statistical Techniques in Pattern Recognition, SPR 2018 - Beijing, China Duration: 17 Aug 2018 → 19 Aug 2018

Publication series

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

Conference

Conference	Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2018 and Statistical Techniques in Pattern Recognition, SPR 2018
Country/Territory	China
City	Beijing
Period	17/08/18 → 19/08/18

Funding

Acknowledgments. This work is supported by the National Natural Science Foundation of China (Grant no. 61602535, 61503422 and 61773415), the Open Projects Program of National Laboratory of Pattern Recognition, and the program for innovation research in Central University of Finance and Economics.

Keywords

Attributed graphs
Entropy
Local-global graph kernels

Access to Document

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

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 et al. / 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 = aug,

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",

note = "Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2018 and Statistical Techniques in Pattern Recognition, SPR 2018 ; Conference date: 17-08-2018 Through 19-08-2018",

}

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 et al.
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/Published conference output › Conference publication

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 - https://www.scopus.com/pages/publications/85052211769

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 publication

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

T2 - Joint IAPR International Workshops on Structural and Syntactic Pattern Recognition, SSPR 2018 and Statistical Techniques in Pattern Recognition, SPR 2018

Y2 - 17 August 2018 through 19 August 2018

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)). doi: 10.1007/978-3-319-97785-0_48

A mixed entropy local-global reproducing kernel for attributed graphs

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this