2026-08-10T22:31:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23249 2025-10-27T10:36:14Z ddc:004 open_access

CluStRE: Streaming Graph Clustering with Multi-Stage Refinement Chhabra, Adil Dorian Peretz, Shai Schulz, Christian graph clustering community streaming online memetic evolutionary We present CluStRE, a novel streaming graph clustering algorithm that balances computational efficiency with high-quality clustering using multi-stage refinement. Unlike traditional in-memory clustering approaches, CluStRE processes graphs in a streaming setting, significantly reducing memory overhead while leveraging re-streaming and evolutionary heuristics to improve solution quality. Our method dynamically constructs a quotient graph, enabling modularity-based optimization while efficiently handling large-scale graphs. We introduce multiple configurations of CluStRE to provide trade-offs between speed, memory consumption, and clustering quality. Experimental evaluations demonstrate that CluStRE improves solution quality by 89.8%, operates 2.6× faster, and uses less than two-thirds of the memory required by the state-of-the-art streaming clustering algorithm on average. Moreover, our strongest mode enhances solution quality by up to 150% on average. With this, CluStRE achieves comparable solution quality to in-memory algorithms, i.e. over 96% of the quality of clustering approaches, including Louvain, effectively bridging the gap between streaming and traditional clustering methods. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adil Chhabra and Shai Dorian Peretz and Christian Schulz 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.11 urn:nbn:de:0030-drops-232493 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode