Automatic Data Grouping: LSEnet and the Future of Self-Organizing Networks

Table of Links

Abstract and 1. Introduction

2. Related Work

3. Preliminaries and Notations

4. Differentiable Structural Information

   4.1. A New Formulation

   4.2. Properties

   4.3. Differentiability & Deep Graph Clustering

5. LSEnet

   5.1. Embedding Leaf Nodes

   5.2. Learning Parent Nodes

   5.3. Hyperbolic Partitioning Tree

6. Experiments

   6.1. Graph Clustering

   6.2. Discussion on Structural Entropy

7. Conclusion, Broader Impact, and References Appendix

A. Proofs

B. Hyperbolic Space

C. Technical Details

D. Additional Results

7. Conclusion

In this paper, we study graph clustering without predefined cluster number from a new perspective of structural entropy. We formulate a new graph clustering objective (DSI) not requiring the cluster number, so that the clusters are revealed in the optimal partitioning tree given by DSI minimization. Furthermore, we present a neural LSEnet to learn the optimal tree in hyperbolic space, where we integrate node features to structural information with Lorentz graph convolution net. Extensive empirical results show the superiority of our approach on real graphs.

Broader Impact

This paper presents work whose goal is to bridge the structural entropy of information theory and deep learning and shows a new objective function for deep graph clustering, not requiring the predefined cluster number. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

References

Almahairi, A., Ballas, N., Cooijmans, T., Zheng, Y., Larochelle, H., and Courville, A. Dynamic capacity networks. In Proceedings of the ICML, pp. 2549–2558. PMLR, 2016.

Bachmann, G., Becigneul, G., and Ganea, O. Constant cur- ´ vature graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119, pp. 486–496. PMLR, 2020.

Becigneul, G. and Ganea, O. Riemannian adaptive opti- ´ mization methods. In Proceedings of 7th International Conference on Learning Representation (ICLR), 2019.

Becigneul, G. and Ganea, O.-E. Riemannian Adaptive Optimization Methods. In International Conference on Learning Representations, 2018.

Bianconi, G. Entropy of network ensembles. Physical Review E, 79(3):036114, 2009.

Braunstein, S. L., Ghosh, S., and Severini, S. The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states. Annals of Combinatorics, 10(3):291–317, 2006.

Chami, I., Ying, Z., Re, C., and Leskovec, J. Hyperbolic ´ graph convolutional neural networks. In Advances in the 32nd NeurIPS, pp. 4869–4880, 2019.

Chami, I., Gu, A., Chatziafratis, V., and Re, C. From trees ´ to continuous embeddings and back: Hyperbolic hierarchical clustering. In Advances in NeurIPS, volume 33, pp. 15065–15076, 2020.

Chen, W., Han, X., Lin, Y., Zhao, H., Liu, Z., Li, P., Sun, M., and Zhou, J. Fully hyperbolic neural networks. In Proceedings of the 60th ACL, pp. 5672–5686, 2022.

Cohen-addad, V., Kanade, V., Mallmann-trenn, F., and Mathieu, C. Hierarchical clustering: Objective functions and algorithms. Journal of the ACM, 66(4):26:1–26:42, 2019.

Devvrit, F., Sinha, A., Dhillon, I., and Jain, P. S3GC: Scalable self-supervised graph clustering. In Advances in NeurIPS, pp. 3248–3261, 2022.

Ester, M., Kriegel, H., Sander, J., and Xu, X. A densitybased algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd KDD, pp. 226–231. AAAI Press, 1996.

Fu, X., Li, J., Wu, J., Sun, Q., Ji, C., Wang, S., Tan, J., Peng, H., and Yu, P. S. ACE-HGNN: adaptive curvature exploration hyperbolic graph neural network. In Proceedings of the ICDM, pp. 111–120. IEEE, 2021.

Fu, X., Wei, Y., Sun, Q., Yuan, H., Wu, J., Peng, H., and Li, J. Hyperbolic geometric graph representation learning for hierarchy-imbalance node classification. In Proceedings of the ACM Web Conference 2023, pp. 460–468. ACM, 2023.

Gershman, S. J. and Blei, D. M. A Tutorial on Bayesian Nonparametric Models, 2011.

Hamilton, W. L., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. In Advances in the 30th NeurIPS, pp. 1024–1034, 2017.

Hassani, K. and Ahmadi, A. H. K. Contrastive multi-view representation learning on graphs. In Proceedings of the 37th ICML, volume 119, pp. 4116–4126, 2020.

Jia, Y., Zhang, Q., Zhang, W., and Wang, X. Communitygan: Community detection with generative adversarial nets. In Proceedings of the WWW, pp. 784–794. ACM, 2019.

Kipf, T. N. and Welling, M. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.

Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th ICLR, 2017.

Krioukov, D. V., Papadopoulos, F., Kitsak, M., Vahdat, A., and Bogun˜a, M. Hyperbolic geometry of complex net- ´ works. Physics Review E, 82(036106), 2010.

Li, A. and Pan, Y. Structural information and dynamical complexity of networks. IEEE Transactions on Information Theory, 62(6):3290–3339, 2016.

Li, B., Jing, B., and Tong, H. Graph communal contrastive learning. In Proceedings of The ACM Web Conference, pp. 1203–1213. ACM, 2022.

Liu, Y., Liu, J., Zhang, Z., Zhu, L., and Li, A. REM: from structural entropy to community structure deception. In Advances in the 32nd NeurIPS, pp. 12918–12928, 2019.

Liu, Y., Tu, W., Zhou, S., Liu, X., Song, L., Yang, X., and Zhu, E. Deep graph clustering via dual correlation reduction. In Proceedings of the 36th AAAI, pp. 7603– 7611. AAAI Press, 2022a.

Liu, Y., Zheng, Y., Zhang, D., Chen, H., Peng, H., and Pan, S. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022, pp. 1392–1403, 2022b.

Liu, Y., Liang, K., Xia, J., Yang, X., Zhou, S., Liu, M., Liu, X., and Li, S. Z. Reinforcement graph clustering with unknown cluster number. In Proceedings of the 31st ACM MM, pp. 3528–3537. ACM, 2023a.

Liu, Y., Liang, K., Xia, J., Zhou, S., Yang, X., Liu, X., and Li, S. Z. Dink-net: Neural clustering on large graphs. In Proceedings of the ICML, volume 202, pp. 21794–21812. PMLR, 2023b.

Liu, Y., Xia, J., Zhou, S., Yang, X., Liang, K., Fan, C., Zhuang, Y., Li, S. Z., Liu, X., and He, K. A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource, 2023c.

Lou, A., Katsman, I., Jiang, Q., Belongie, S. J., Lim, S., and Sa, C. D. Differentiating through the frechet mean. ´ In Proceedings of the 37th ICML, volume 119 of Proceedings of Machine Learning Research, pp. 6393–6403. PMLR, 2020.

Mrabah, N., Bouguessa, M., and Ksantini, R. Escaping feature twist: A variational graph auto-encoder for node clustering. In Proceedings of the 31st IJCAI, pp. 3351– 3357. ijcai.org, 2022.

Nickel, M. and Kiela, D. Poincare embeddings for learn- ´ ing hierarchical representations. In Advances in 30th NeurIPS, pp. 6338–6347, 2017.

Pan, E. and Kang, Z. Multi-view contrastive graph clustering. In Advances in NeurIPS, pp. 2148–2159, 2021.

Pan, S., Hu, R., Long, G., Jiang, J., Yao, L., and Zhang, C. Adversarially regularized graph autoencoder for graph embedding. In Proceedings of the 27th IJCAI, pp. 2609– 2615. ijcai.org, 2018.

Perozzi, B., Al-Rfou, R., and Skiena, S. Deepwalk: Online learning of social representations. In Proceedings of the 20th KDD, pp. 701–710. ACM, 2014.

Sarkar, R. Low distortion delaunay embedding of trees in hyperbolic plane. In Proceedings of the 19th International Symposium on Graph Drawing (Eindhoven, The Netherlands), volume 7034, pp. 355–366. Springer, 2011.

Schubert, E. Stop using the elbow criterion for k-means and how to choose the number of clusters instead. SIGKDD Explor., 25(1):36–42, 2023.

Shannon, C. E. A mathematical theory of communication. The Bell System Technical Journal, 27(3):379–423, 1948.

Sun, L., Zhang, Z., Zhang, J., Wang, F., Peng, H., Su, S., and Yu, P. S. Hyperbolic variational graph neural network for modeling dynamic graphs. In Proceedings of the 35th AAAI, pp. 4375–4383, 2021.

Sun, L., Ye, J., Peng, H., and Yu, P. S. A self-supervised riemannian GNN with time varying curvature for temporal graph learning. In Proceedings of the 31st ACM CIKM, pp. 1827–1836, 2022a.

Sun, L., Zhang, Z., Ye, J., Peng, H., Zhang, J., Su, S., and Yu, P. S. A self-supervised mixed-curvature graph neural network. In Proceedings of the 36th AAAI, pp. 4146– 4155, 2022b.

Sun, L., Huang, Z., Wu, H., Ye, J., Peng, H., Yu, Z., and Yu, P. S. Deepricci: Self-supervised graph structurefeature co-refinement for alleviating over-squashing. In Proceedings of the 23rd ICDM, pp. 558–567, 2023a.

Sun, L., Wang, F., Ye, J., Peng, H., and Yu, P. S. CONGREGATE: contrastive graph clustering in curvature spaces. In Proceedings of the 32nd IJCAI, pp. 2296–2305. ijcai.org, 2023b.

Sun, L., Ye, J., Peng, H., Wang, F., and Yu, P. S. Selfsupervised continual graph learning in adaptive riemannian spaces. In Proceedings of the 37th AAAI, pp. 4633– 4642, 2023c.

Sun, L., Hu, J., Li, M., and Peng, H. R-ode: Ricci curvature tells when you will be informed. In Proceedings of the ACM SIGIR, 2024a.

Sun, L., Hu, J., Zhou, S., Huang, Z., Ye, J., Peng, H., Yu, Z., and Yu, P. S. Riccinet: Deep clustering via a riemannian generative model. In Proceedings of the ACM Web Conference 2024 (WWW’24), 2024b.

Sun, L., Huang, Z., Wang, Z., Wang, F., Peng, H., and Yu, P. S. Motif-aware riemannian graph neural network with generative-contrastive learning. In Proceedings of the 38th AAAI, pp. 9044–9052, 2024c.

Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. In ` Proceedings of the 6th ICLR, 2018.

Wang, T., Mirzazadeh, F., Zhang, X., and Chen, J. Gc-flow: A graph-based flow network for effective clustering. In Proceedings of the ICML, volume 202, pp. 36157–36173. PMLR, 2023.

Wu, J., Chen, X., Xu, K., and Li, S. Structural entropy guided graph hierarchical pooling. In Proceedings of the 39th ICML, pp. 24017–24030. PMLR, 2022.

Wu, J., Chen, X., Shi, B., Li, S., and Xu, K. SEGA: structural entropy guided anchor view for graph contrastive learning. In Proceedings of the 40th ICML, volume 202, pp. 37293–37312. PMLR, 2023.

Xia, J., Wu, L., Wang, G., Chen, J., and Li, S. Z. Progcl: Rethinking hard negative mining in graph contrastive learning. In Proceedings of the ICML, volume 162, pp. 24332–24346. PMLR, 2022.

Xie, J., Girshick, R., and Farhadi, A. Unsupervised deep embedding for clustering analysis. In Proceedings of the ICML, pp. 478–487. PMLR, 2016.

Xiong, B., Zhu, S., Potyka, N., Pan, S., Zhou, C., and Staab, S. Pseudo-riemannian graph convolutional networks. In Advances in NeurIPS, 2022.

Yang, C., Liu, M., Wang, Z., Liu, L., and Han, J. Graph clustering with dynamic embedding. arXiv preprint arXiv:1712.08249, 2017.

Yang, L., Wang, Y., Gu, J., Wang, C., Cao, X., and Guo, Y. JANE: jointly adversarial network embedding. In Proceedings of the 29th IJCAI, pp. 1381–1387. ijcai.org, 2020.

Yang, M., Zhou, M., Ying, R., Chen, Y., and King, I. Hyperbolic representation learning: Revisiting and advancing. In Proceedings of the 40th ICML. PMLR, 2023a.

Yang, Z., Zhang, G., Wu, J., Yang, J., Sheng, Q. Z., Peng, H., Li, A., Xue, S., and Su, J. Minimum entropy principle guided graph neural networks. In Proceedings of the 16th ACM WSDM, pp. 114–122, 2023b.

Yin, H., Benson, A. R., Leskovec, J., and Gleich, D. F. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD, pp. 555–564. ACM, 2017.

Zhang, Y., Wang, X., Shi, C., Liu, N., and Song, G. Lorentzian graph convolutional networks. In Proceedings of the Web Conference 2021, pp. 1249–1261. ACM / IW3C2, 2021.

Zou, D., Peng, H., Huang, X., Yang, R., Li, J., Wu, J., Liu, C., and Yu, P. S. Se-gsl: A general and effective graph structure learning framework through structural entropy optimization. In Proceedings of the ACM Web Conference, pp. 499–510, 2023.