Research map / Learning theory and algorithms / Clustering
Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a single-pass semi-streaming algorithm with O(n polylog n) memory for a (2+ε)-approximate directed densest subgraph on randomized streams, using sampling and a Set-Sample routine, plus MPC round improvements and experiments versus Bahmani et al.
Problem
Finding a (2+ε)-approximate directed densest subgraph in large graphs under streaming and MPC constraints; prior single-pass methods needed O(n^1.5) memory and prior O(n polylog n)-memory methods needed O(log n) passes.
Approach
Reuses edges already in memory and samples the remaining stream via a Set-Sample routine with an estimated edge count, so vertex degrees for peeling are estimated without new passes; the MPC variant simulates the stream by sampling edge batches from relevant remaining edges, shrinking them by n^delta per step.
Key results
- Single-pass semi-streaming algorithm gives a 2(1+ε)-approximation (up to constants) with O(n log^2 n/ε^3) memory, improving on Esfandiari et al.'s O(n^1.5) memory and Bahmani et al.'s O(log n) passes.
- MPC: O(1) rounds in super-linear memory n^(1+δ) and O(sqrt(log n)) rounds in near-linear memory, versus O(log n) rounds for prior directed methods.
- Empirically, the algorithm's density is within 3% of Bahmani et al. and about 2x faster on large graphs (up to 4x on PrefAttach 2); it is 1.5% more accurate on Twitter and 5.5% on LiveJournal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Single-pass sampling-based semi-streaming algorithm (on randomized streams) vs Bahmani et al. multi-pass peeling | directed densest subgraph · 6 benchmarks, arbitrary-ordered streams | density quality: within 3% of baseline | No clear effect |
| Single-pass sampling algorithm instead of Bahmani et al. | large directed graphs · LiveJournal | density: +5.5% | Helped |
| Single-pass sampling algorithm instead of Bahmani et al. | large directed graphs · Twitter | density: +1.5% | Helped |
| Single-pass sampling algorithm instead of Bahmani et al. | denser graphs · PrefAttach 2 | running time: around 4x faster | Helped |
| Single-pass sampling algorithm instead of Bahmani et al. | denser graphs · Twitter | running time: around 2.5x faster | Helped |
| Sample size parameter f reduced (sparser samples, f=1/450) (ablation) | single-pass sampling algorithm · 6 benchmarks | density | No clear effect |
| Stream randomization (randomized vs arbitrary order) (ablation) | single-pass sampling algorithm · benchmarks | performance | No clear effect |
Surprising findings
- Algorithm remains accurate on non-randomly ordered streams in experiments, even though guarantees require randomized streams.
- Sampling with a small constant (f = 1/450) still gives densities close to the baseline.
Limitations
- Guarantees for the single-pass algorithm require randomized stream order; experiments on arbitrary order are empirical only.
- MPC near-linear regime gives a 2+ε approximation rather than 1+ε.
- Still requires O(log n) passes in the non-randomized setting; the single-pass result depends on randomization.
Experimental setup
Datasets: Slashdot Berkeley-Stanford Web Graph LiveJournal Twitter PrefAttach 1 PrefAttach 2
Benchmarks: Slashdot Berkeley-Stanford Web Graph LiveJournal Twitter PrefAttach 1 PrefAttach 2
Metrics: density running time
Baselines: Bahmani et al. (VLDB 2012) Algorithm 3 Esfandiari et al. (2015)
Builds on: Bahmani et al. directed densest subgraph peeling Esfandiari et al. sampling for densest subgraph Chernoff bound
Closest papers by meaning
- New Parallel and Streaming Algorithms for Directed Densest Subgraph (NeurIPS 2025 · similarity 0.96)
- Efficient Streaming Algorithms for Graphlet Sampling (NeurIPS 2024 · similarity 0.88)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.88)
- Densest k-Subgraph Mining via a Provably Tight Relaxation (AAAI 2025 · similarity 0.88)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.87)
- Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.