Table of Links Abstract and 1. Introduction Abstract and 1. Introduction Abstract and 1. Introduction Related Work


Preliminaries and Notations


Differentiable Structural Information
4.1. A New Formulation
4.2. Properties
4.3. Differentiability & Deep Graph Clustering


LSEnet
5.1. Embedding Leaf Nodes
5.2. Learning Parent Nodes
5.3. Hyperbolic Partitioning Tree


Experiments
6.1. Graph Clustering
6.2. Discussion on Structural Entropy


Conclusion, Broader Impact, and References Appendix Related Work Related Work Related Work Related Work Preliminaries and Notations Preliminaries and Notations Preliminaries and Notations Preliminaries and Notations Differentiable Structural Information
4.1. A New Formulation
4.2. Properties
4.3. Differentiability & Deep Graph Clustering Differentiable Structural Information Differentiable Structural Information Differentiable Structural Information 4.1. A New Formulation 4.1. A New Formulation 4.2. Properties 4.2. Properties 4.3. Differentiability & Deep Graph Clustering 4.3. Differentiability & Deep Graph Clustering LSEnet
5.1. Embedding Leaf Nodes
5.2. Learning Parent Nodes
5.3. Hyperbolic Partitioning Tree LSEnet LSEnet LSEnet 5.1. Embedding Leaf Nodes 5.1. Embedding Leaf Nodes 5.2. Learning Parent Nodes 5.2. Learning Parent Nodes 5.3. Hyperbolic Partitioning Tree 5.3. Hyperbolic Partitioning Tree Experiments
6.1. Graph Clustering
6.2. Discussion on Structural Entropy Experiments Experiments 6.1. Graph Clustering 6.1. Graph Clustering 6.2. Discussion on Structural Entropy 6.2. Discussion on Structural Entropy Conclusion, Broader Impact, and References Appendix Conclusion, Broader Impact, and References Appendix Conclusion, Broader Impact, and References Appendix Conclusion, Broader Impact, and References Appendix A. Proofs A. Proofs B. Hyperbolic Space B. Hyperbolic Space C. Technical Details C. Technical Details D. Additional Results D. Additional Results Abstract Graph clustering is a fundamental problem in machine learning. Deep learning methods achieve the state-of-the-art results in recent years, but they still cannot work without predefined cluster numbers. Such limitation motivates us to pose a more challenging problem of graph clustering with unknown cluster number. We propose to address this problem from a fresh perspective of graph information theory (i.e., structural information). In the literature, structural information has not yet been introduced to deep clustering, and its classic definition falls short of discrete formulation and modeling node features. In this work, we first formulate a differentiable structural information (DSI) in the continuous realm, accompanied by several theoretical results. By minimizing DSI, we construct the optimal partitioning tree where densely connected nodes in the graph tend to have the same assignment, revealing the cluster structure. DSI is also theoretically presented as a new graph clustering objective, not requiring the predefined cluster number. Furthermore, we design a neural LSEnet in the Lorentz model of hyperbolic space, where we integrate node features to structural information via manifold-valued graph convolution. Extensive empirical results on real graphs show the superiority of our approach. 1. Introduction Graph clustering aims to group the nodes into several clusters, and routinely finds itself in applications ranging from biochemical analysis to community detection (Jia et al., 2019; Liu et al., 2023c). With the advance of graph neural networks (Kipf & Welling, 2017; Velickovic et al., 2018), deep graph clustering (Devvrit et al., 2022; Wang et al., 2023) achieves remarkable success in recent years. So far, deep graph clustering still cannot work without a predefined cluster number K, and thus one needs to correctly predict the cluster number before clustering, which is often impractical in real cases. Also, estimating cluster numbers is nontrivial. Empirical methods such as Elbow or Bayesian information criterion need to train the deep model repeatedly (Schubert, 2023), and computation cost is much too expensive. For the clustering without graph structures, possible solutions free of K include Bayesian non-parametric methods (Gershman & Blei, 2011), density-based models, e.g., DBSCAN (Ester et al., 1996), and hierarchical clustering (Cohen-addad et al., 2019). However, they cannot be directly applied to graphs owing to the inter-correlation among the nodes. That is, the problem of graph clustering with unknown cluster number largely remains open. the problem of graph clustering with unknown cluster number largely remains open. In this work, we present a fresh perspective of information theory. Stemming from Shannon entropy, structural information (Li & Pan, 2016) is formulated to measure the uncertainty on graphs. Minimizing the structural information, an optimal partitioning tree is constructed to describe the graph’s self-organization without the knowledge of cluster number. It sheds light on the targeted problem but presents several significant gaps to deep clustering in the meantime. First and foremost, the clustering ability of structural entropy is still unclear. In the literature, structural information has not yet been introduced to deep clustering, though it has been receiving research attention recently (Liu et al., 2019; Wu et al., 2023; Zou et al., 2023). Second, the discrete formulation prevents the gradient backpropagation, posing a fundamental challenge to train a deep model. Third, the classic definition neglects the node features, which are often equally important to graph clustering. structural information In light of the aforementioned issues, we present a novel differentiable structural information (DSI) in the continuous realm. DSI is formulated with level-wise assignment matrices and is equivalent to the classic formulation under binary assignment. In fact, the conductance for graph clustering is inherently related to DSI. The intuition is that in the partitioning tree T of DSI minimization, the densely connected nodes in the graph tend to be assigned to the same parent node, minimizing the conductance and presenting the cluster structure. Thus DSI emerges as a new graph clustering objective, not requiring the predefined cluster number. Next, we consider a partitioning tree Tnet learned by a neural network, given that our objective supports gradient backpropagation for the network. We show that the structural entropy of the optimal Tnet well approximates that of Li & Pan (2016) under slight constraint. Furthermore, we design a Lorentz Structural Entropy neural net (LSEnet) to learn Tnet (as shown in Figure 1) in the Lorentz model of hyperbolic space, where we further integrate node features to structural information via graph convolution net. Specifically, we first embed the leaf nodes of the partitioning tree, and then recursively learn the parent nodes from bottom to top (root node), where the level-wise parent assignment is attentively determined by the proposed Lorentz assigner. Consequently, LSEnet combines the advantages of both structural entropy and hyperbolic space for graph clustering. The main contributions are listed as follows. • We study a challenging yet practical problem of graph clustering with unknown cluster number and, to our best knowledge, make the first attempt to bridge deep graph clustering and structural information. • We present the differentiable structural information (DSI), generalizing the classic theory to the continuous realm. DSI emerges as a new graph clustering objective, not requiring the cluster number. • We design a novel hyperbolic LSEnet with graph neural network, further integrating the structural information and node features. Extensive empirical results show the superiority of LSEnet for graph clustering. This paper is available on arxiv under CC BY-NC-SA 4.0 Deed (Attribution-Noncommercial-Sharelike 4.0 International) license. This paper is available on arxiv under CC BY-NC-SA 4.0 Deed (Attribution-Noncommercial-Sharelike 4.0 International) license. available on arxiv available on arxiv Authors:
(1) Li Sun, North China Electric Power University, Beijing 102206, China (ccesunli@ncepu.edu);
(2) Zhenhao Huang, North China Electric Power University, Beijing 102206, China;
(3) Hao Peng, Beihang University, Beijing 100191, China;
(4) Yujie Wang, North China Electric Power University, Beijing 102206, China;
(5) Chunyang Liu, Didi Chuxing, Beijing, China;
(6) Philip S. Yu, University of Illinois at Chicago, IL, USA. Authors: Authors: (1) Li Sun, North China Electric Power University, Beijing 102206, China (ccesunli@ncepu.edu); (2) Zhenhao Huang, North China Electric Power University, Beijing 102206, China; (3) Hao Peng, Beihang University, Beijing 100191, China; (4) Yujie Wang, North China Electric Power University, Beijing 102206, China; (5) Chunyang Liu, Didi Chuxing, Beijing, China; (6) Philip S. Yu, University of Illinois at Chicago, IL, USA.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

LSEnet: Deep Graph Clustering with Unknown Cluster Numbers via Lorentz Hyperbolic Space

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Comparative Performance Analysis of SymTax on Five Citation Recommendation Datasets

It Is Okay If You Don't Know What You Like. We Do (feat. Deep Recommendation Algorithms)

10 Machine Learning, Data Science, and Deep Learning Courses for Programmers in 2020

10 Computer Vision Startups on Product Hunt with the Most Upvotes

10 Best Entry Level Machine Learning Tutorials

10 Best + Free Machine Learning Courses Collection

A Comparative Performance Analysis of SymTax on Five Citation Recommendation Datasets

It Is Okay If You Don't Know What You Like. We Do (feat. Deep Recommendation Algorithms)

10 Machine Learning, Data Science, and Deep Learning Courses for Programmers in 2020

10 Computer Vision Startups on Product Hunt with the Most Upvotes

10 Best Entry Level Machine Learning Tutorials

10 Best + Free Machine Learning Courses Collection

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps