DDGC: A diffusion-based approach for dynamic graph clustering.

Abstract

In this paper, we propose a novel diffusion model-based dynamic graph clustering method to address the challenge of evolving graph structures, where new nodes may belong to unknown classes. Existing deep graph clustering approaches exhibit strong performance on static graphs but fail to handle dynamic scenarios where both graph topology and node categories evolve over time. Moreover, few existing dynamic graph clustering methods discuss the complex setting where minority-class samples and dynamic class growth coexist. Our method integrates graph convolutional networks (GCN) with diffusion models, leveraging data density fluctuations in the embedding space to assign pseudo-labels for unsupervised learning. Specifically, we extend diffusion models by incorporating kernel density estimation and Tweedie's formula to guide density regularization in low-density regions, thereby enhancing the accuracy of new class identification. It also directs data to converge toward high-density regions, thus improving the model's performance and robustness under weak density variations. Experimental results on benchmark datasets demonstrate that our approach outperforms state-of-the-art baselines in dynamic graph clustering tasks, particularly in scenarios involving emerging unknown classes. The proposed framework achieves adaptive class discovery and sample augmentation, exhibiting robust performance in both static and evolving graph environments. This work bridges the gap between traditional static graph clustering and real-world dynamic applications, offering a modular solution for online graph understanding.