Structural Entropy Guided Graph Hierarchical Pooling

Junran Wu, Xueyuan Chen, Ke Xu, Shangzhe Li
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:24017-24030, 2022.

Abstract

Following the success of convolution on non-Euclidean space, the corresponding pooling approaches have also been validated on various tasks regarding graphs. However, because of the fixed compression ratio and stepwise pooling design, these hierarchical pooling methods still suffer from local structure damage and suboptimal problem. In this work, inspired by structural entropy, we propose a hierarchical pooling approach, SEP, to tackle the two issues. Specifically, without assigning the layer-specific compression ratio, a global optimization algorithm is designed to generate the cluster assignment matrices for pooling at once. Then, we present an illustration of the local structure damage from previous methods in reconstruction of ring and grid synthetic graphs. In addition to SEP, we further design two classification models, SEP-G and SEP-N for graph classification and node classification, respectively. The results show that SEP outperforms state-of-the-art graph pooling methods on graph classification benchmarks and obtains superior performance on node classifications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-wu22b, title = {Structural Entropy Guided Graph Hierarchical Pooling}, author = {Wu, Junran and Chen, Xueyuan and Xu, Ke and Li, Shangzhe}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {24017--24030}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/wu22b/wu22b.pdf}, url = {https://proceedings.mlr.press/v162/wu22b.html}, abstract = {Following the success of convolution on non-Euclidean space, the corresponding pooling approaches have also been validated on various tasks regarding graphs. However, because of the fixed compression ratio and stepwise pooling design, these hierarchical pooling methods still suffer from local structure damage and suboptimal problem. In this work, inspired by structural entropy, we propose a hierarchical pooling approach, SEP, to tackle the two issues. Specifically, without assigning the layer-specific compression ratio, a global optimization algorithm is designed to generate the cluster assignment matrices for pooling at once. Then, we present an illustration of the local structure damage from previous methods in reconstruction of ring and grid synthetic graphs. In addition to SEP, we further design two classification models, SEP-G and SEP-N for graph classification and node classification, respectively. The results show that SEP outperforms state-of-the-art graph pooling methods on graph classification benchmarks and obtains superior performance on node classifications.} }
Endnote
%0 Conference Paper %T Structural Entropy Guided Graph Hierarchical Pooling %A Junran Wu %A Xueyuan Chen %A Ke Xu %A Shangzhe Li %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-wu22b %I PMLR %P 24017--24030 %U https://proceedings.mlr.press/v162/wu22b.html %V 162 %X Following the success of convolution on non-Euclidean space, the corresponding pooling approaches have also been validated on various tasks regarding graphs. However, because of the fixed compression ratio and stepwise pooling design, these hierarchical pooling methods still suffer from local structure damage and suboptimal problem. In this work, inspired by structural entropy, we propose a hierarchical pooling approach, SEP, to tackle the two issues. Specifically, without assigning the layer-specific compression ratio, a global optimization algorithm is designed to generate the cluster assignment matrices for pooling at once. Then, we present an illustration of the local structure damage from previous methods in reconstruction of ring and grid synthetic graphs. In addition to SEP, we further design two classification models, SEP-G and SEP-N for graph classification and node classification, respectively. The results show that SEP outperforms state-of-the-art graph pooling methods on graph classification benchmarks and obtains superior performance on node classifications.
APA
Wu, J., Chen, X., Xu, K. & Li, S.. (2022). Structural Entropy Guided Graph Hierarchical Pooling. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:24017-24030 Available from https://proceedings.mlr.press/v162/wu22b.html.

Related Material