Dense Subgraph Clustering and a New Cluster Ensemble Method

The-Anh Vu-Le 1 [0000-0002-4480-5535], João Alfredo Cardoso Lamy 2 [0009-0005-4744-4754], Tomás Alessi 2 [0009-0006-2658-5758], Ian Chen 1 [0009-0000-3777-3603], Minhyuk Park 1 [0000-0002-8676-7565], Elfarouk Harb 1 [0000-0002-7770-0932], George Chacko 1 [0000-0002-2127-1892], Tandy Warnow 1 [0000-0 · 2025

Read Dense Subgraph Clustering and a New Cluster Ensemble Method by The-Anh Vu-Le 1 [0000-0002-4480-5535], João Alfredo Cardoso Lamy 2 [0009-0005-4744-4754], Tomás Alessi 2 [0009-0006-2658-5758], Ian Chen 1 [0009-0000-3777-3603], Minhyuk Park 1 [0000-0002-8676-7565], Elfarouk Harb 1 [0000-0002-7770-0932], George Chacko 1 [0000-0002-2127-1892], Tandy Warnow 1 [0000-0 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-17013.txt.

Introduction

The-Anh Vu-Le, Tandy Warnow, and six co-authors cluster network data by pulling out dense knots. Their paper, from twenty twenty-five, presents DSC-Flow-Iter. The method lifts out tightly linked groups one by one. It leaves many nodes ungrouped, yet its groups are rarely wrong.

That care makes it a good partner for modularity methods, which group broadly but sloppily. The team builds an ensemble that merges both styles of output. On many fake networks with known groups, the blend beats each part alone. It also beats other standard tools. The work is aimed at fields like biology, where networks are large and truth is partly known.

Catalog record

CREATORThe-Anh Vu-Le 1 [0000-0002-4480-5535], João Alfredo Cardoso Lamy 2 [0009-0005-4744-4754], Tomás Alessi 2 [0009-0006-2658-5758], Ian Chen 1 [0009-0000-3777-3603], Minhyuk Park 1 [0000-0002-8676-7565], Elfarouk Harb 1 [0000-0002-7770-0932], George Chacko 1 [0000-0002-2127-1892], Tandy Warnow 1 [0000-0
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-17013

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dense Subgraph Clustering and a New Cluster Ensemble Method The-Anh Vu-Le 1 [0000-0002-4480-5535], João Alfredo Cardoso Lamy 2 [0009-0005-4744-4754], Tomás Alessi 2 [0009-0006-2658-5758], Ian Chen 1 [0009-0000-3777-3603], Minhyuk Park 1 [0000-0002-8676-7565], Elfarouk Harb 1 [0000-0002-7770-0932], George Chacko 1 [0000-0002-2127-1892], Tandy Warnow 1 [0000-0001-7717-3514] Abstract We propose DSC-Flow-Iter, a new community detection algorithm that is based on iterative extraction of dense subgraphs. Although DSC-Flow-Iter leaves many nodes unclustered, it is competitive with leading methods and has high-precision and low-recall, making it complementary to modularity-based methods that typically have high recall but lower precision. Based on this observation, we introduce a novel cluster ensemble technique that combines DSC-Flow-Iter with modularity-based clustering, to provide improved accuracy. We show that our proposed pipeline, which uses this ensemble technique, outperforms its individual components and improves upon the baseline techniques on a large collection of synthetic networks. † † institute: 1 School of Computing and Data Science, University of Illinois Urbana-Champaign, Urbana IL 61801 2 Insper Institute, Sao Paolo, Brazil , WWW home page: https://tandy.cs.illinois.edu 1 Introduction Community detection, also known as graph clustering, is the task of partitioning a network’s vertices into groups that exhibit strong community structure. In general, the groups should exhibit strong edge density (i.e., many edges connecting nodes within groups), they should be well-connected (i.e., they should not have small edge cuts), and there should be relatively fewer edges between different groups yang2012defining . Identifying these structures can be helpful for understanding the organization and function of complex systems across various domains, from bioinformatics, social networks, and scientific research networks su2022comprehensive . Community detection is often posed as an optimization problem, with modularity one of the best known optimization problems newman2004detecting . Since these problems are generally NP-hard, finding optimal solutions is not reliable, and heuristics, such as Leiden leiden and Louvain louvain , are used. The Iterative k-Core (IKC) algorithm ikc is an example of an alternative approach, which focuses on the iterative extraction of high-quality subgraphs. Given the network, IKC finds a k -core (i.e., a subgraph in which all nodes have degree at least k ) for the largest achieved value of k , treats the k -core as a community and then removes it, and recurses until a stopping rule applies (e.g., no k -cores for k>10 are left). This iterative approach provides the motivation for our proposed method, which replaces the k -core concept with a different measure of density. We examine clustering methods that use greedy iterative approaches based on seeking subgraphs that have the largest edge density harb2022faster , where the density of a subgraph is the ratio of the number of edges to the number of vertices. The Dense Subgraph Decomposition procedure described in harb2022faster partitions the vertex set of the input graph G=(V,E) into a series of subsets based on decreasing density. The process begins by identifying S_{1} , which is the unique maximal densest subgraph in the graph G . Subsequently, for each step i , the procedure identifies the maximal set S from the remaining vertices that maximizes the function (|E(S)|+|E(S,U_{i-1})|)/|S| , where U_{i-1} is the union of all previously identified subsets S_{1},\dots,S_{i-1} , E(S) is the set of edges between vertices of S (i.e., E(S)=\{\{u,v\}\in E\mid u,v\in S\} ), and E(S,S^{\prime}) is the set of edges between vertices of S and S^{\prime} (i.e., E(S,S^{\prime})=\{\{u,v\}\in E\mid u\in S,v\in S^{\prime}\} ). Notice that |E(S)|/|S| is the density of the subgraph induced by S . Hence, this approach differs from a simple iterative extraction of the densest subgraph since it also accounts for the edges connecting a candidate subgraph to the parts that have already been extracted. Harb and colleagues proposed two main approaches to compute a dense subgraph decomposition: FISTA harb2022faster , which solves a convex relaxation of the problem using the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA), and Flow harb2025corporate , which solves a max-flow formulation of the problem using a push-relabel solver. The Flow technique is expected to provide better accuracy than FISTA. We study the application of FISTA and Flow within an iterative framework, and find that our new approach (DSC-Flow-Iter), described in greater detail below, provides the best accuracy of these density-based methods. DSC-Flow-Iter is not quite as accurate as the best standard method we evaluated (i.e., Leiden-CPM, followed by postprocessing using WCC park2024improved-arxiv ), but a new cluster ensemble approach we present here that combines DSC-Flow-Iter with other techniques attains higher accuracy than all tested methods. Due to space restrictions, full details and some results are provided in the Supplementary Materials, available at the DSC-Flow-Iter github site dsc-github . 2 Materials and Methods We present an overview of the methods we studied and the experiments we performed to evaluate these methods. The data used in this study are available from prior publications (see ecsbm_benchmark ). The software for the DSC-Flow-Iter and ensemble methods are available at dsc-github and clustermerger-github . The software for other methods as well as the specific commands used are detailed in Supplementary Materials Section 2. 2.1 Datasets Real-world networks We use a collection of 78 real-world networks sourced from the Netzschleuder database netzschleuder and from Park24-11-CM-journal . These networks span various domains, including social networks, collaboration networks, web graphs, and communication networks. Their sizes range from 906 to 14 million of nodes. A complete list of these networks is available in the Supplementary Materials Section 1. For evaluating clustering accuracy of different methods, we excluded the 4 largest networks ( livejournal , orkut , bitcoin , and CEN ) and generated synthetic networks based on the remaining 74 ; the largest of these networks has 1.4 million nodes. For evaluating computational performance, we used all 78 networks. Synthetic networks We use EC-SBM vu2025ecsbm to generate synthetic networks based on 74 of the real-world networks we studied. EC-SBM takes as input the parameters obtained from a clustered network and generates a synthetic network that aims to reproduce the cluster and network statistics. For this study, we used 74 of the real-world networks we studied, with the input clustering obtained using Stochastic Block Models (SBMs) computed using graph-tool graph-tool , and then post-processed using Well Connected Clusters (WCC, see below) to ensure that the clusters are well-connected. This input clustering approach was selected because vu2025ecsbm established that it provides the closest fit to the network and clustering statistics. 2.2 Clustering Methods We compared density-based clustering methods to standard clustering methods, including Leiden optimizing modularity (Leiden-Mod), Leiden optimizing under the Constant Potts Model (Leiden-CPM), Infomap, and IKC. Of these, only the density-based methods are new, and so we describe these further. Density-based techniques We adapt the Flow and FISTA algorithms harb2022faster ; harb2025corporate as follows. Each of these methods computes values for the vertices so that all vertices with the same values will be put into the same cluster. The values produced by FISTA are approximate and cannot be used naively. Therefore, we apply a simple rounding heuristic, grouping nodes whose values round to the same integer. Since these groups may contain two or more connected components, we divide them into connected components, and call this method DSC-FISTA(int). In contrast, the values produced by Flow can be used directly (i.e., no rounding is needed, although division

Read the complete text