Riemannian Graph Learning & Structural Entropy: Deep Node Clustering in 2026
Table of Links
-
Experiments
2. Related Work
Deep Graph Clustering. Deep models have achieved state-of-the-art results in node clustering. Classic methods leverage a reconstructive loss to learn node representations, while identifying node clusters with distance-based or model-based algorithms (e.g., k-means, Gaussian mixture model) (Xie et al., 2016; Almahairi et al., 2016; Yang et al., 2017). Other methods learn cluster assignment with generative adversarial nets (Yang et al., 2020; Jia et al., 2019). Contrastive clustering explores the similarity on the graph itself, pulling positive samples together and pushing negative ones apart (Devvrit et al., 2022; Pan & Kang, 2021; Li et al., 2022). Sun et al. (2023b) consider contrastive graph clustering in the product manifold with a loss of Ricci curvature. Normalizing flows have recently been introduced to graph clustering (Wang et al., 2023). Few deep model is built without the predefined cluster number, to the best of our knowledge. Very recently, Liu et al. (2023a) focus on automatically estimating the number of clusters via reinforcement learning, which is orthogonal to our study.
Structural Entropy. Information entropy is a key notation of information theory (Shannon, 1948), measuring the amount of information for unstructured data, and it fails to study the information on graphs. On information measure for graphs, early practices, e.g., Von Neumann entropy (Braunstein et al., 2006) and Gibbs entropy (Bianconi, 2009), are still defined by unstructured probability distributions, and the graph structure is degenerated. Recently, structural entropy is proposed in account of the natural selforganizing in the graphs (Li & Pan, 2016), and has been successfully applied to graph pooling (Wu et al., 2022), adversarial attack (Liu et al., 2019), contrastive learning (Wu et al., 2023), dimension estimation (Yang et al., 2023b) and graph structural learning (Zou et al., 2023). However, structural entropy has not yet been introduced to deep clustering, and the gap roots in the discrete formulation of Li & Pan (2016). Besides, it falls short of considering node features that are important to graph clustering as well.
Riemannian Graph Learning. Euclidean space has been the workhorse of graph learning for decades (Perozzi et al., 2014; Kipf & Welling, 2017; Velickovic et al., 2018). In recent years, Riemannian manifolds have emerged as an exciting alternative. Hyperbolic models (Nickel & Kiela, 2017; Chami et al., 2019; Sun et al., 2021; 2022a; 2023c; Zhang et al., 2021; Yang et al., 2023a; Fu et al., 2023) achieve remarkable success on the graphs dominated by tree-like structures (Krioukov et al., 2010). In fact, an arbitrary tree can be embedded in hyperbolic space with bounded distortion (Sarkar, 2011). Fu et al. (2021) study the optimal curvature of hyperbolic space for graph embedding. Beyond hyperbolic space, the product manifolds (Sun et al., 2022b; 2024c) show its superiority on generic graph structures. Recently, Ricci curvature of Riemannian geometry is given a differentiable surrogate for graph structural learning (Sun et al., 2023a). Manifold vector fields (ordinary differential equations) (Sun et al., 2024b) are introduced to study information diffusion on the graphs (Sun et al., 2024a). Note that, the inherent connection between the tree and hyperbolic space supports the construction of our model.
:::info
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.
:::
:::info
This paper is available on arxiv under CC BY-NC-SA 4.0 Deed (Attribution-Noncommercial-Sharelike 4.0 International) license.
:::
