Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs

Costas Mavromatis; George Karypis

doi:10.1007/978-3-030-75762-5_43

Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs

Costas Mavromatis, George Karypis

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

53 Scopus citations

Abstract

This work proposes a new unsupervised (or self-supervised) node representation learning method that aims to leverage the coarse-grain information that is available in most graphs. This extends previous attempts that only leverage fine-grain information (similarities within local neighborhoods) or global graph information (similarities across all nodes). Intuitively, the proposed method identifies nodes that belong to the same clusters and maximizes their mutual information. Thus, coarse-grain (cluster-level) similarities that are shared between nodes are preserved in their representations. The core components of the proposed method are (i) a jointly optimized clustering of nodes during learning and (ii) an Infomax objective term that preserves the mutual information among nodes of the same clusters. Our method is able to outperform competing state-of-art methods in various downstream tasks, such as node classification, link prediction, and node clustering. Experiments show that the average gain is between 0.2% and 6.1%, over the best competing approach, over all tasks. Our code is publicly available at: https://github.com/cmavro/Graph-InfoClust-GIC.

Original language	English (US)
Title of host publication	Advances in Knowledge Discovery and Data Mining - 25th Paciﬁc-Asia Conference, PAKDD 2021, Proceedings
Editors	Kamal Karlapalem, Hong Cheng, Naren Ramakrishnan, R. K. Agrawal, P. Krishna Reddy, Jaideep Srivastava, Tanmoy Chakraborty
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	541-553
Number of pages	13
ISBN (Print)	9783030757618
DOIs	https://doi.org/10.1007/978-3-030-75762-5_43
State	Published - May 9 2021
Event	25th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2021 - Virtual, Online Duration: May 11 2021 → May 14 2021

Publication series

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

Conference

Conference	25th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2021
City	Virtual, Online
Period	5/11/21 → 5/14/21

Bibliographical note

Funding Information:
This work was supported in part by NSF (1447788, 1704074, 1757916, 1834251), Army Research Office (W911NF1810344), Intel Corp, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute.

Funding Information:
Acknowledgements. This work was supported in part by NSF (1447788, 1704074, 1757916, 1834251), Army Research Office (W911NF1810344), Intel Corp, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Publisher link

10.1007/978-3-030-75762-5_43

Find It

Find It at U of M Libraries

Cite this

Mavromatis, C., & Karypis, G. (2021). Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs. In K. Karlapalem, H. Cheng, N. Ramakrishnan, R. K. Agrawal, P. K. Reddy, J. Srivastava, & T. Chakraborty (Eds.), Advances in Knowledge Discovery and Data Mining - 25th Paciﬁc-Asia Conference, PAKDD 2021, Proceedings (pp. 541-553). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12712 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-75762-5_43

Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs. / Mavromatis, Costas; Karypis, George.
Advances in Knowledge Discovery and Data Mining - 25th Paciﬁc-Asia Conference, PAKDD 2021, Proceedings. ed. / Kamal Karlapalem; Hong Cheng; Naren Ramakrishnan; R. K. Agrawal; P. Krishna Reddy; Jaideep Srivastava; Tanmoy Chakraborty. Springer Science and Business Media Deutschland GmbH, 2021. p. 541-553 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12712 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Mavromatis, C & Karypis, G 2021, Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs. in K Karlapalem, H Cheng, N Ramakrishnan, RK Agrawal, PK Reddy, J Srivastava & T Chakraborty (eds), Advances in Knowledge Discovery and Data Mining - 25th Paciﬁc-Asia Conference, PAKDD 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12712 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 541-553, 25th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2021, Virtual, Online, 5/11/21. https://doi.org/10.1007/978-3-030-75762-5_43

Mavromatis C, Karypis G. Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs. In Karlapalem K, Cheng H, Ramakrishnan N, Agrawal RK, Reddy PK, Srivastava J, Chakraborty T, editors, Advances in Knowledge Discovery and Data Mining - 25th Paciﬁc-Asia Conference, PAKDD 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 541-553. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-75762-5_43

Mavromatis, Costas ; Karypis, George. / Graph InfoClust : Maximizing Coarse-Grain Mutual Information in Graphs. Advances in Knowledge Discovery and Data Mining - 25th Paciﬁc-Asia Conference, PAKDD 2021, Proceedings. editor / Kamal Karlapalem ; Hong Cheng ; Naren Ramakrishnan ; R. K. Agrawal ; P. Krishna Reddy ; Jaideep Srivastava ; Tanmoy Chakraborty. Springer Science and Business Media Deutschland GmbH, 2021. pp. 541-553 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{98262892e8504fcf9f5857ab574de3bb,

title = "Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs",

abstract = "This work proposes a new unsupervised (or self-supervised) node representation learning method that aims to leverage the coarse-grain information that is available in most graphs. This extends previous attempts that only leverage fine-grain information (similarities within local neighborhoods) or global graph information (similarities across all nodes). Intuitively, the proposed method identifies nodes that belong to the same clusters and maximizes their mutual information. Thus, coarse-grain (cluster-level) similarities that are shared between nodes are preserved in their representations. The core components of the proposed method are (i) a jointly optimized clustering of nodes during learning and (ii) an Infomax objective term that preserves the mutual information among nodes of the same clusters. Our method is able to outperform competing state-of-art methods in various downstream tasks, such as node classification, link prediction, and node clustering. Experiments show that the average gain is between 0.2% and 6.1%, over the best competing approach, over all tasks. Our code is publicly available at: https://github.com/cmavro/Graph-InfoClust-GIC.",

author = "Costas Mavromatis and George Karypis",

note = "Funding Information: This work was supported in part by NSF (1447788, 1704074, 1757916, 1834251), Army Research Office (W911NF1810344), Intel Corp, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute. Funding Information: Acknowledgements. This work was supported in part by NSF (1447788, 1704074, 1757916, 1834251), Army Research Office (W911NF1810344), Intel Corp, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 25th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2021 ; Conference date: 11-05-2021 Through 14-05-2021",

year = "2021",

month = may,

day = "9",

doi = "10.1007/978-3-030-75762-5_43",

language = "English (US)",

isbn = "9783030757618",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "541--553",

editor = "Kamal Karlapalem and Hong Cheng and Naren Ramakrishnan and Agrawal, {R. K.} and Reddy, {P. Krishna} and Jaideep Srivastava and Tanmoy Chakraborty",

booktitle = "Advances in Knowledge Discovery and Data Mining - 25th Paciﬁc-Asia Conference, PAKDD 2021, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Graph InfoClust

T2 - 25th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2021

AU - Mavromatis, Costas

AU - Karypis, George

N1 - Funding Information: This work was supported in part by NSF (1447788, 1704074, 1757916, 1834251), Army Research Office (W911NF1810344), Intel Corp, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute. Funding Information: Acknowledgements. This work was supported in part by NSF (1447788, 1704074, 1757916, 1834251), Army Research Office (W911NF1810344), Intel Corp, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute. Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021/5/9

Y1 - 2021/5/9

N2 - This work proposes a new unsupervised (or self-supervised) node representation learning method that aims to leverage the coarse-grain information that is available in most graphs. This extends previous attempts that only leverage fine-grain information (similarities within local neighborhoods) or global graph information (similarities across all nodes). Intuitively, the proposed method identifies nodes that belong to the same clusters and maximizes their mutual information. Thus, coarse-grain (cluster-level) similarities that are shared between nodes are preserved in their representations. The core components of the proposed method are (i) a jointly optimized clustering of nodes during learning and (ii) an Infomax objective term that preserves the mutual information among nodes of the same clusters. Our method is able to outperform competing state-of-art methods in various downstream tasks, such as node classification, link prediction, and node clustering. Experiments show that the average gain is between 0.2% and 6.1%, over the best competing approach, over all tasks. Our code is publicly available at: https://github.com/cmavro/Graph-InfoClust-GIC.

AB - This work proposes a new unsupervised (or self-supervised) node representation learning method that aims to leverage the coarse-grain information that is available in most graphs. This extends previous attempts that only leverage fine-grain information (similarities within local neighborhoods) or global graph information (similarities across all nodes). Intuitively, the proposed method identifies nodes that belong to the same clusters and maximizes their mutual information. Thus, coarse-grain (cluster-level) similarities that are shared between nodes are preserved in their representations. The core components of the proposed method are (i) a jointly optimized clustering of nodes during learning and (ii) an Infomax objective term that preserves the mutual information among nodes of the same clusters. Our method is able to outperform competing state-of-art methods in various downstream tasks, such as node classification, link prediction, and node clustering. Experiments show that the average gain is between 0.2% and 6.1%, over the best competing approach, over all tasks. Our code is publicly available at: https://github.com/cmavro/Graph-InfoClust-GIC.

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

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

U2 - 10.1007/978-3-030-75762-5_43

DO - 10.1007/978-3-030-75762-5_43

M3 - Conference contribution

AN - SCOPUS:85111098601

SN - 9783030757618

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

SP - 541

EP - 553

BT - Advances in Knowledge Discovery and Data Mining - 25th Paciﬁc-Asia Conference, PAKDD 2021, Proceedings

A2 - Karlapalem, Kamal

A2 - Cheng, Hong

A2 - Ramakrishnan, Naren

A2 - Agrawal, R. K.

A2 - Reddy, P. Krishna

A2 - Srivastava, Jaideep

A2 - Chakraborty, Tanmoy

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 11 May 2021 through 14 May 2021

ER -

Graph InfoClust: Maximizing Coarse-Grain Mutual Information in Graphs

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this