Research map / Learning theory and algorithms / Sample complexity
New Parallel and Streaming Algorithms for Directed Densest Subgraph
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 sublinear-memory MPC and deterministic single-pass semi-streaming (and insertion-only dynamic) algorithms for directed densest subgraph, using fixed degree thresholds with a (1+ε)-factor stopping rule, freezing/sampling for MPC round reduction, and level-based degree counting for streaming.
Problem
Computing approximate directed densest subgraphs in massively parallel computation (MPC), semi-streaming, and dynamic models, where prior MPC and streaming methods need many rounds or only achieve poor approximations in a single pass.
Approach
Peeling with fixed degree thresholds k_S = D/(2z), k_T = Dz/2 plus a (1+ε)-shrink stopping rule; MPC version simulates O(√log n) peeling iterations per phase via graph exponentiation after freezing high-degree vertices and sampling edges; streaming version tracks per-vertex levels using only degree counters.
Key results
- MPC algorithm gives a 2(1+ε)^6-approximation in Õ(√log n) rounds with O(n^δ) memory per machine, improving over O(log n) rounds of prior directed MPC work.
- Deterministic single-pass semi-streaming algorithm gives an O(log n)-approximation for directed DS, versus Ω̃(n^{1/6}) implied for prior uniform-sampling style single-pass approaches.
- On temporal datasets with ε=0.2, the single-pass algorithm's density matches the O(log n)-pass (2+ε)-approximation of Bahmani et al.; in MPC simulations it uses fewer than half the rounds of prior work at the same memory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sublinear memory per machine for the MPC algorithm | Proposed directed densest subgraph MPC algorithm · Directed densest subgraph, MPC | memory per machine: $\tilde{O}(n)$ -> $O(n^\delta)$ | Helped |
| Apply the proposed sublinear-memory MPC algorithm instead of Bahmani et al. | Directed densest subgraph · Directed densest subgraph, MPC | round complexity: $O(\log n)$ -> $\tilde{O}(\sqrt{\log n})$ | Helped |
| Apply the proposed MPC algorithm instead of Mitrović & Pan | Directed densest subgraph · Directed densest subgraph, MPC | memory per machine: $\tilde{O}(n)$ -> $O(n^\delta)$ | Helped |
| Use a deterministic single-pass algorithm on arbitrary streams | Directed densest subgraph · Arbitrary semi-streaming stream | approximation factor: $\tilde{\Omega}(n^{1/6})$ -> $O(\log n)$ | Helped |
| Use the proposed semi-streaming algorithm on temporal datasets | Directed densest subgraph · Temporal directed graphs | density | No clear effect |
| Use the proposed semi-streaming algorithm instead of the prior method on temporal graphs | Directed densest subgraph · Temporal directed graphs | sensitivity to error in $z^2$ | Helped |
| Use the proposed MPC algorithm instead of the prior directed-graph MPC algorithm | Directed densest subgraph · MPC simulations on evaluated datasets | rounds: less than half the number of rounds | Helped |
| Randomize the edge order | Proposed semi-streaming algorithm · General directed graphs | density | Helped |
| Use the proposed semi-streaming algorithm on endpoint-sorted general graphs | Directed densest subgraph · General directed graphs | density: within a factor of around 2 | Mixed |
Surprising findings
- Empirically the single-pass algorithm's density on temporal datasets matches a multi-pass baseline, far better than its O(log n) worst-case guarantee.
- Even with adversarially sorted edge orders, densities are within about a factor of 2 of the multi-pass baseline on general datasets.
Limitations
- MPC approximation is 2(1+ε)^6 rather than the (1+ε) of undirected/other directed MPC methods; round complexity still Õ(√log n).
- Single-pass streaming guarantee is only O(log n), not constant-factor; no constant-approximation single-pass for directed graphs.
- MPC experiments were simulated centrally rather than run on a real distributed framework.
Experimental setup
Datasets: Slashdot Google Web Berkeley-Stanford Web Pokec LiveJournal Ask Ubuntu Super User Wikipedia Twitter Stack Overflow
Benchmarks: Stanford Large Network Dataset Collection (10 directed graphs)
Metrics: density approximation ratio vs z^2 update time per edge batch MPC rounds
Baselines: Bahmani et al. O(log n)-pass peeling Mitrovic & Pan randomized single-pass algorithm Mitrovic & Pan MPC algorithm Bhattacharya et al. dynamic algorithm
Builds on: Bahmani et al. directed densest subgraph peeling graph exponentiation Bhattacharya et al. dynamic densest subgraph
Closest papers by meaning
- Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · 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)
- Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems (ICML 2024 · similarity 0.87)
- Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.87)
- Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.87)
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.