Source-linked AI summary
Finding Many Overlapping Dense Subgraphs Using Triadic Cohorts
Sabyasachi Basu, C. Seshadhri
TL;DR
The paper addresses the lack of scalable methods that jointly find overlapping dense subgraphs and cover large portions of sparse real-world graphs. It introduces triadic cohorts and CohortRecovery, which provably approximates these structures and performs strongly in experiments. The method often covers substantial graph regions with dense subgraphs, captures curated ground-truth clusters, and typically runs within minutes on commodity hardware.
Problem
Existing methods either find many dense subgraphs without overlap or produce overlapping clusters without dense-subgraph guarantees, limiting coverage of real-world graphs.
Method
CohortRecovery defines triangle-rich triadic cohorts and outputs dense subgraphs that approximately contain every identifiable cohort.
Results
CohortRecovery achieves the highest coverage in almost all of 18 datasets, captures curated ground-truth clusters, and nearly perfectly recovers overlapping stochastic-block-model structure.
Takeaways & Limitations
The framework provides a provable and practical route to recovering overlapping dense structure across large real-world graphs.
Takeaways & Limitations
The paper excludes GNN methods from comparison because of scalability, hardware, and clustering-performance concerns, and notes challenges in proving neighborhood exploration captures almost an entire cohort.
Abstract
from arXiv · showhide
Graphs are a standard representation for data in the social sciences, cybersecurity, computer infrastructure, bioinformatics, and more. Typical real-world graphs are sparse, meaning the average degree is small (in the tens, while the number of vertices is more than millions). When graph data is collected from a source, a major task is to perform data exploration. Thus, any region of ``density" is of interest, since it indicates special structure. An important goal is to cover a significant portion of the graph using dense subgraphs. Existing algorithms that find many dense subgraphs do not have overlapping output, and hence provide limited coverage. Other methods that produce overlapping clusters do not generate dense subgraphs. The main goal of this paper is to develop provable and practical methods that can provide overlapping dense subgraphs that can cover large portions of real-world networks. Our contribution is an algorithm CohortRecovery that achieves this goal. We first develop a mathematical framework of triadic cohorts that captures the notion of ``detectable dense subgraphs'' that potentially overlap. We prove that CohortRecovery can output a set of dense subgraphs, such that each triadic cohort is almost completely contained in some dense subgraph. We give a practical implementation of CohortRecovery and demonstrate it on a variety of datasets. It typically runs in under ten minutes on a commodity machine even on graphs with tens of millions of edges. For numerous datasets, CohortRecovery is able to cover more than 25\% of the vertices in non-trivial subgraphs of density more than 0.8, and is significantly better than a wide variety of scalable graph clustering/community detection algorithms. Moreover, we demonstrate that output of CohortRecovery captures ground truth clusters obtained by manual curation.
1 Introduction
The paper targets scalable discovery of many overlapping dense subgraphs, addressing the limited coverage of methods that find only a few dense sets or partition graphs. CohortRecovery combines a theoretical triadic-cohort framework with practical recovery and achieves broad empirical coverage.
- Motivation: Real-world graphs are sparse, so dense regions can indicate special structure worth exploring.The paper notes that average degree is often in the tens despite graphs having millions or more vertices.
- Motivation: Most dense-subgraph methods seek one or a few large sets, limiting coverage of the graph.The paper argues that data analysis often requires many dense subgraphs rather than a single optimal set.
- Motivation: More than 30% of the graph belongs to multiple ground-truth clusters in many datasets, motivating overlapping output.Many methods instead construct partitions, which do not represent this overlap.
- Approach: CohortRecovery is designed to cover large portions of real-world graphs with overlapping dense subgraphs while providing theoretical grounding.The framework aims to recover well-structured dense subgraphs approximately and evaluate the algorithm empirically.
- Contributions: CohortRecovery defines triangle-rich triadic cohorts and gives a polynomial-time algorithm for approximately covering every such cohort.Its running time is subquadratic in the triangle count, and the cohort notion supports nearly exact recovery of all cohorts.
- Empirical findings: On 18 datasets, CohortRecovery has the highest coverage in almost all cases, with nearly double the coverage of previous methods on several datasets.Coverage counts vertices in sufficiently dense subsets after removing sets of size at most four; comparisons include triangle-based, modularity, and overlapping-cluster methods.
- Empirical findings: CohortRecovery performs best on curated ground-truth comparisons in all but one dataset and can nearly perfectly recover overlapping stochastic-block-model structure.The paper also reports improvements of 7 percent over previous methods in numerous datasets.
- Scope: The paper does not compare with GNN methods because they often lack scalability, require specialized hardware, or show weaker clustering performance.The cited discussion notes that many GNN approaches work only on graphs with fewer than a million vertices.
2 The problem setup
The paper models recoverable dense structure as overlapping triadic cohorts defined by low diameter, triangle richness, and expansion. CohortRecovery outputs dense sets that approximately contain every identifiable cohort without assumptions on cohort overlap or distribution.
- Framework: The framework seeks approximate dense-subgraph recovery for potentially overlapping structures in an input graph.It treats triadic cohorts as a proxy for ground-truth dense substructures in noisy exploratory data.
- Algorithm: The algorithm grows candidate clusters from a vertex neighborhood by absorbing triangles, aiming to produce dense, triangle-dense structures that contain cohorts.The implementation uses pruning and neighborhood exploration while original degrees remain fixed for analysis.
- Cohort definition: Triadic cohorts require low diameter, triangle-rich edges, and expansion across small vertex subsets.The diameter is at most 2; each edge participates in sufficiently many triangles; and every small subset has many outgoing edges.
- Identifiability: Triadic cohorts may overlap or contain one another, so identifiable cohorts additionally require a vertex specific to that cohort.A sole member has limited triangle participation with third vertices outside the cohort.
- Guarantee: For every identifiable ε-triadic cohort, CohortRecovery outputs a set containing at least a (1 − γ)-fraction of its vertices.Every output set has edge density at least Ωε,γ(1), and the output family has size Oε(|V(H)|) for each cohort H.
- Guarantee: The theorem imposes no assumption on the structure, overlap, or distribution of cohorts.With constant ε and γ, output sets have constant density and each identifiable cohort is almost completely contained in an output set only a constant factor larger.
- Structural properties: Every triadic cohort has comparable vertex degrees, a neighborhood of at least ε|V(H)|, and edge density Ω(ε).These properties follow from triangle richness and the diameter-two condition.
3 The algorithm
CohortRecovery cleans the graph, selects independent-set seeds, and grows seed neighborhoods by absorbing triangle-rich vertices and red-edge cores. Its analysis shows that outputs remain dense, nearly capture every triadic cohort, and admit a provable running-time bound.
- High-level algorithm: CohortRecovery first removes edges with too few triangles, deletes isolated vertices, and constructs a maximal independent set of seeds.Each seed invokes bag to construct an output cluster.
- Cluster growth: Each seed starts with its neighborhood and repeatedly adds vertices supported by many internal triangles or sufficiently dense cores of red edges.Red edges participate in many triangles whose third vertex is already in the current cluster.
- Seed selection: The independent-set seeds suffice to capture all triadic cohorts without assumptions about how those cohorts intersect.A maximal independent set provides seeds that are sufficiently separated while still covering the graph.
- Cluster growth: The core-growth step prevents triangle density from being diluted when many cohort triangles have one vertex inside the cluster and two outside.Adding individual outside edges would bring in too few triangles per added vertex, whereas sufficiently large red-edge k-cores preserve the needed structure.
- Guarantees: Every output cluster has size O_ε,γ(d_i) and density Ω_ε,γ(1), while some output contains a (1 − γ)-fraction of each identifiable ε-triadic cohort.The proof also establishes that the cleaning phase preserves all edges of ε-triadic cohorts.
- Complexity: An implementation runs in O_ε,γ((m + n + R) log n + t max_i √t_i) time and uses O(m + n + t) storage.Here t is the number of triangles, t_i is the triangle count incident to vertex i, and R is the triangle-enumeration time.
4 Empirical evaluation
CohortRecovery is evaluated across public datasets against dense-subgraph, community-detection, and overlapping-clustering methods. It achieves broad high-density coverage, competitive ground-truth recovery, and practical runtimes.
- Experimental setup: Experiments use public undirected datasets, remove self-loops, and include seven datasets with curated ground-truth clusters.The evaluation compares CohortRecovery with triangle-based, structural-entropy, k-truss, modularity, and PageRank-based methods.
- Experimental setup: Ground-truth datasets contain substantial overlap: many vertices appear in multiple labeled clusters.The evaluation notes that overlap is a significant aspect of the ground-truth cluster structure except in two datasets.
- Main findings: At density 0.5, CohortRecovery has the highest coverage on all but three datasets and exceeds 0.3 coverage on eleven of eighteen datasets.Coverage is computed over output clusters with at least five vertices.
- Main findings: At density 0.8, CohortRecovery has the highest coverage on all eighteen datasets.Nucleus runs out of memory on the hollywood dataset in the reported experiments.
- Main findings: CohortRecovery finishes within an hour on every dataset, typically requiring seconds to minutes even for very large graphs.The implementation uses a single tunable parameter ε, set to 0.1; coverage generally declines as ε increases beyond 0.2.
- Main findings: CohortRecovery wins on ground-truth-oriented MaxPrec in five of six overlapping datasets.The ground-truth evaluation retains clusters of size at least five before intersection, while nonempty intersections remain eligible afterward.
- Main findings: On a computer-science citation network, the method finds tens of thousands of significantly overlapping topic-coherent clusters.The example concerns papers on reconfigurable systems and illustrates why a partition can make clusters incomplete.
A.1 Proofs from §2.1
The appendix supplies proofs supporting the paper’s degree-based dense-subgraph lemma and an associated probabilistic claim.
- Proofs from §2.1: Lemma 2.6 uses the Matula-Beck minimum-degree removal procedure to show that a sufficiently dense vertex set leaves an edge before all its vertices are removed.The proof compares the set’s initial edge count with the number of edges removed while deleting vertices below degree r/2.
- Proofs from §2.1: The appendix completes Claim 2.7 by rearranging a probabilistic expectation expression.The displayed expression includes a contribution from the event X > E[X]/2.
A.2 Proofs from §3.1
The proof of Claim 3.2 analyzes triangle participation around vertices and relates neighboring degrees within CohortRecovery’s intermediate graphs.
- Proofs from §3.1: Claim 3.2 shows that every neighbor v of i in G′ satisfies d_v ≤ d_i/ε when each incident edge participates in enough triangles.This degree relation places all such neighbors in G′′ and supports a lower bound on i’s degree there.
A.3 Runtime Analysis
The runtime analysis bounds the cost of triangle-based cleaning and bag processing, then aggregates these costs over all calls. The proof uses triangle enumeration, indexed storage, priority queues, and core decomposition.
- Cleaning operation: The cleaning operation runs in O((m + n + R) log n) time and uses O(m + n + t) storage after enumerating triangles.Edges with triangle count below ε max(d_u, d_v) are removed while the triangle data structure is updated.
- Bag processing: For each nonzero-degree vertex i, bag processing takes O_ε,γ(d_i^3) time by enumerating incident triangles and maintaining indexed structures.The analysis bounds triangle enumeration and the number of vertices added to the cohort set C.
- Bag processing: Priority-queue updates and linear-time core decomposition remain within the same O_ε,γ(d_i^3) bound for each bag call.Each sufficiently dense core adds Ω_ε,γ(d_i) vertices, so only O_ε,γ(1) such events occur.
- Overall runtime: The per-vertex bag bounds are summed over all i to obtain the total runtime for CohortRecovery.The supplied proof concludes this aggregation after establishing the individual call bounds.
A.4 Empirical running time breakdown
The empirical runtime breakdown shows that initial cleaning usually dominates CohortRecovery, although cluster extraction is largest in some datasets. Berkstan and hollywood take disproportionately longer because they contain notably large clusters.
- Runtime components: Initial cleaning is typically the largest runtime component, while cluster extraction dominates in some datasets.Figure 3 breaks runtime down across the components of CohortRecovery.
- Dataset variation: Berkstan and hollywood take disproportionately more time for their size, and hollywood produces larger clusters than the other datasets.The larger clusters may explain hollywood’s higher running time.
A.5 Examples of dense subgraphs
The citation-network example produces many semantically meaningful, overlapping clusters whose intersections correspond to coherent reconfigurable-systems subfields. The table highlights papers shared across those subfields.
- Citation-network example: CohortRecovery finds tens of thousands of clusters in the AMiner computer-science citation network, many of them semantically meaningful.The example contains three intersecting output sets.
- Intersection analysis: The three intersecting clusters concern reconfigurable architecture generation, instruction set customization, and task scheduling.Table 5 identifies these as the coherent sub-fields represented in the overlap.
A.6 Studies with varying ε
The study varies ε from 0.05 to 0.5 and measures coverage by the fraction of vertices in sufficiently large, sufficiently dense subsets. Very small ε values produce low-density outputs, while coverage drops sharply beyond ε = 0.2.
- Effect of ε: When ε ≤ 0.01, edge removal is ineffective and the output sets have low density.At ε = 0, no edge is deleted and the entire graph is returned as one cluster.
A.7 Results on SBMs
On disjoint and overlapping SBMs, CohortRecovery recovers planted blocks with high recall and precision, while comparator methods show weaker cluster isolation or precision. On overlapping SBMs, Nucleus retains slightly higher recall but produces more mixed clusters.
- Evaluation metrics: Recall and MaxPrec are averaged over planted blocks within each randomized instance, then across instances, using output clusters with at least five vertices.The evaluation also reports the number of output clusters meeting the five-vertex threshold.
- Experimental setup: 30 independently generated SBM instances evaluate recovery under disjoint and overlapping planted-block structures.Disjoint graphs contain 20 blocks over 2000 vertices; overlapping graphs contain 26 sequentially overlapping blocks over 1975 vertices.
- Disjoint SBMs: On disjoint SBMs, CohortRecovery and Nucleus achieve near-perfect recall and MaxPrec, whereas CoDeSEG has substantially lower MaxPrec.The lower MaxPrec indicates that many planted blocks are not cleanly recovered by CoDeSEG.
- Overlapping SBMs: On overlapping SBMs, Nucleus achieves slightly higher recall than CohortRecovery but much lower MaxPrec, indicating greater mixing of planted blocks.CoDeSEG degrades further in the overlapping setting.
- Output redundancy: CohortRecovery and Nucleus both show output redundancy, while CohortRecovery's number of outputs with at least five vertices decreases as pin increases.This pattern occurs in both disjoint and overlapping settings.