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

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

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.

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.

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.