# Revisiting Dynamic Graph Clustering via Matrix Factorization

Source: [Revisiting Dynamic Graph Clustering via Matrix Factorization](<https://www.sota2.com/research/paper/68fa76e31e209131cea6fa9a>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T04:04:15.628Z

Authors: Dongyuan Li, Satoshi Kosugi, Ying Zhang, Manabu Okumura, Feng Xia, Renhe Jiang

Published: 2025-02-10T02:57:46.000Z

## Abstract

Dynamic graph clustering aims to detect and track time-varying clusters in dynamic graphs, revealing the evolutionary mechanisms of complex real-world dynamic systems. Matrix factorization-based methods are promising approaches for this task; however, these methods often struggle with scalability and can be time-consuming when applied to large-scale dynamic graphs. Moreover, they tend to lack robustness and are vulnerable to real-world noisy data. To address these issues, we make three key contributions. First, to improve scalability, we propose temporal separated matrix factorization, where a single matrix is divided into multiple smaller matrices for independent factorization, resulting in faster computation. Second, to improve robustness, we introduce bi-clustering regularization, which jointly optimizes graph embedding and clustering, thereby filtering out noisy features from the graph embeddings. Third, to further enhance effectiveness and efficiency, we propose selective embedding updating, where we update only the embeddings of dynamic nodes while the embeddings of static nodes are fixed among different timestamps. Experimental results on six synthetic and five real-world benchmarks demonstrate the scalability, robustness and effectiveness of our proposed method. Source code is available at https://github.com/Clearloveyuan/DyG-MF.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Graph Clustering on BD-30K](<https://www.sota2.com/research/sota/graph-clustering-on-bd-30k.md>): Graph Clustering; BD-30K; NMI: 99.9.

- [Graph Clustering on EC-30K](<https://www.sota2.com/research/sota/graph-clustering-on-ec-30k.md>): Graph Clustering; EC-30K; NMI: 99.2.

- [Graph Clustering on Wikipedia](<https://www.sota2.com/research/sota/graph-clustering-on-wikipedia.md>): Graph Clustering; Wikipedia; NMI: 0.504.

- [Graph Clustering on Dublin](<https://www.sota2.com/research/sota/graph-clustering-on-dublin.md>): Graph Clustering; Dublin; NMI: 56.1.

- [Graph Clustering on arXiv](<https://www.sota2.com/research/sota/graph-clustering-on-arxiv.md>): Graph Clustering; arXiv; NMI: 51.8.

- [Graph Clustering on DR 100K](<https://www.sota2.com/research/sota/graph-clustering-on-dr-100k.md>): Graph Clustering; DR 100K; NMI: 94.3.

- [Graph Clustering on MS 100K](<https://www.sota2.com/research/sota/graph-clustering-on-ms-100k.md>): Graph Clustering; MS 100K; NMI: 94.4.

- [Graph Clustering on SO](<https://www.sota2.com/research/sota/graph-clustering-on-so.md>): Graph Clustering; SO; NMI: 45.5.

- [Graph Clustering on Flickr](<https://www.sota2.com/research/sota/graph-clustering-on-flickr.md>): Graph Clustering; Flickr; NMI: 52.3.

- [Graph Clustering on Youtube](<https://www.sota2.com/research/sota/graph-clustering-on-youtube.md>): Graph Clustering; YouTube; NMI: 51.8.

- [Graph Clustering on BD-100K](<https://www.sota2.com/research/sota/graph-clustering-on-bd-100k.md>): Graph Clustering; BD-100K; NMI: 92.3.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2502.06117>)

[PDF](<https://arxiv.org/pdf/2502.06117.pdf>)
