Learning Graph Representation via Graph Entropy Maximization

Ziheng Sun, Xudong Wang, Chris Ding, Jicong Fan
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:47133-47158, 2024.

Abstract

Graph representation learning aims to represent graphs as vectors that can be utilized in downstream tasks such as graph classification. In this work, we focus on learning diverse representations that can capture the graph information as much as possible. We propose quantifying graph information using graph entropy, where we define a probability distribution of a graph based on its nodes’ representations and global-graph representation. However, the computation of graph entropy is NP-hard due to the complex vertex-packing polytope involved in its definition. To address this challenge, we provide an approximation method leveraging orthonormal representations for graph entropy maximization. The proposed method is implemented via graph neural networks, resulting in informative node-level and graph-level representations. Experimental results demonstrate the effectiveness of our method in comparison to many baselines in unsupervised learning and semi-supervised learning tasks. The code of our method is available at https://github.com/MathAdventurer/GeMax.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-sun24i, title = {Learning Graph Representation via Graph Entropy Maximization}, author = {Sun, Ziheng and Wang, Xudong and Ding, Chris and Fan, Jicong}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {47133--47158}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/sun24i/sun24i.pdf}, url = {https://proceedings.mlr.press/v235/sun24i.html}, abstract = {Graph representation learning aims to represent graphs as vectors that can be utilized in downstream tasks such as graph classification. In this work, we focus on learning diverse representations that can capture the graph information as much as possible. We propose quantifying graph information using graph entropy, where we define a probability distribution of a graph based on its nodes’ representations and global-graph representation. However, the computation of graph entropy is NP-hard due to the complex vertex-packing polytope involved in its definition. To address this challenge, we provide an approximation method leveraging orthonormal representations for graph entropy maximization. The proposed method is implemented via graph neural networks, resulting in informative node-level and graph-level representations. Experimental results demonstrate the effectiveness of our method in comparison to many baselines in unsupervised learning and semi-supervised learning tasks. The code of our method is available at https://github.com/MathAdventurer/GeMax.} }
Endnote
%0 Conference Paper %T Learning Graph Representation via Graph Entropy Maximization %A Ziheng Sun %A Xudong Wang %A Chris Ding %A Jicong Fan %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-sun24i %I PMLR %P 47133--47158 %U https://proceedings.mlr.press/v235/sun24i.html %V 235 %X Graph representation learning aims to represent graphs as vectors that can be utilized in downstream tasks such as graph classification. In this work, we focus on learning diverse representations that can capture the graph information as much as possible. We propose quantifying graph information using graph entropy, where we define a probability distribution of a graph based on its nodes’ representations and global-graph representation. However, the computation of graph entropy is NP-hard due to the complex vertex-packing polytope involved in its definition. To address this challenge, we provide an approximation method leveraging orthonormal representations for graph entropy maximization. The proposed method is implemented via graph neural networks, resulting in informative node-level and graph-level representations. Experimental results demonstrate the effectiveness of our method in comparison to many baselines in unsupervised learning and semi-supervised learning tasks. The code of our method is available at https://github.com/MathAdventurer/GeMax.
APA
Sun, Z., Wang, X., Ding, C. & Fan, J.. (2024). Learning Graph Representation via Graph Entropy Maximization. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:47133-47158 Available from https://proceedings.mlr.press/v235/sun24i.html.

Related Material