PaperlayerView exact revision on arXiv

Source-linked AI summary

Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis

arXiv:1504.02268v3cs.DS

TL;DR

The paper addresses how to maintain graph properties on rapidly changing streams while using small space and adapting quickly. It develops a randomized densest-subgraph algorithm based on sampled edges and decomposition techniques, achieving high-probability approximation with near-linear space and near-constant amortized update and query time under an oblivious adversary.

  • Problem

    Maintaining graph properties under edge insertions and deletions requires both small space and rapid adaptation in the one-pass dynamic semi-streaming model.

  • Method

    The algorithm combines random edge sampling through bucketed ℓ0 samplers with an approximate (α, d, L)-decomposition.

  • Results

    A (4+ε)-approximation uses ˜O(n) space, ˜O(1) amortized update time, and O(1) query time with high probability over the first polynomially many updates.

  • Takeaways & Limitations

    The result provides simultaneous time- and space-efficient one-pass maintenance of the densest subgraph in dynamic streams.

  • Takeaways & Limitations

    The stated guarantees apply only to polynomially many updates and assume an oblivious adversary whose update sequence does not depend on the algorithm’s random bits.

Abstract

from arXiv · show

While in many graph mining applications it is crucial to handle a stream of updates efficiently in terms of {\em both} time and space, not much was known about achieving such type of algorithm. In this paper we study this issue for a problem which lies at the core of many graph mining applications called {\em densest subgraph problem}. We develop an algorithm that achieves time- and space-efficiency for this problem simultaneously. It is one of the first of its kind for graph problems to the best of our knowledge. In a graph $G = (V, E)$, the "density" of a subgraph induced by a subset of nodes $S \subseteq V$ is defined as $|E(S)|/|S|$, where $E(S)$ is the set of edges in $E$ with both endpoints in $S$. In the densest subgraph problem, the goal is to find a subset of nodes that maximizes the density of the corresponding induced subgraph. For any $ε>0$, we present a dynamic algorithm that, with high probability, maintains a $(4+ε)$-approximation to the densest subgraph problem under a sequence of edge insertions and deletions in a graph with $n$ nodes. It uses $\tilde O(n)$ space, and has an amortized update time of $\tilde O(1)$ and a query time of $\tilde O(1)$. Here, $\tilde O$ hides a $O(\poly\log_{1+ε} n)$ term. The approximation ratio can be improved to $(2+ε)$ at the cost of increasing the query time to $\tilde O(n)$. It can be extended to a $(2+ε)$-approximation sublinear-time algorithm and a distributed-streaming algorithm. Our algorithm is the first streaming algorithm that can maintain the densest subgraph in {\em one pass}. The previously best algorithm in this setting required $O(\log n)$ passes [Bahmani, Kumar and Vassilvitskii, VLDB'12]. The space required by our algorithm is tight up to a polylogarithmic factor.

1 Introduction

The paper addresses densest-subgraph maintenance on rapidly changing graphs, where both space and update time matter. It presents randomized, deterministic, sublinear-time, distributed-streaming, and directed-graph extensions with explicit approximation and complexity guarantees.

  • Problem and model: The dynamic model supports adversarial edge insertions and deletions while keeping the node set fixed and maintaining an approximation to the densest-subgraph value.The main theorem assumes the update sequence is oblivious to the algorithm’s random bits.
  • Main dynamic result: ˜O(n) space and ˜O(1) amortized update time yield a high-probability (4+ε)-approximation for densest-subgraph values over polynomially many dynamic-stream updates.The algorithm processes the first T=⌈n^λ⌉ updates from an empty graph and maintains the estimate throughout the stream.
  • Approximation trade-off: A (2+ε)-approximation is available with the same space, preprocessing, and update time, but ˜O(n) query time.This strengthens the approximation guarantee at the cost of slower queries.
  • Extensions: The paper also gives ˜O(n)-time sublinear and (2+ε)-approximate distributed-streaming algorithms, plus deterministic and directed-graph extensions.The distributed algorithm uses ˜O(k+n) communication, while the directed extension gives an (8+ε)-approximation with ˜O(m+n) space and ˜O(1) update and query times.
  • Positioning: The main algorithm is presented as the first dynamic graph algorithm combining ˜O(n) space with fast update and query operations for densest subgraph.Earlier insert-only work required O(log_{1+ε} n) passes, whereas this result maintains the estimate during the stream.
  • Technique: The approach uses an (α,d,L)-decomposition, an approximate repeated degree-removal structure that can approximate densest subgraph when L=O(log_{1+ε} n).This structure extends the graph-theoretic d-core and supports both streaming and dynamic algorithms.

2 Notations and Preliminaries

The paper formalizes densest subgraph notation and introduces layered (α, d, L)-decompositions, which approximate maximum density by testing geometrically spaced degree thresholds.

  • The densest subgraph maximizes ρ(S) = |E(S)|/|S| over node subsets S, with n and m denoting the graph’s nodes and edges.
  • For every node set S, average degree satisfies δ(S) = 2ρ(S), linking density to degree-based analysis.
  • The maximum density d∗ lies between m/n and n, providing bounds for selecting threshold values.
  • An (α, d, L)-decomposition forms nested sets that retain nodes above degree αd and exclude nodes below degree d at each level.
  • Testing thresholds d in powers of (1+ε) yields a 2α(1+ε)^2-approximation framework, with the highest nonempty top level identifying the relevant threshold.
  • If d is sufficiently large, decomposition levels shrink; if d is below d∗/α, the final level remains nonempty and some intermediate level has density at least d/(2(1+ε)).

3 A Semi-Streaming Algorithm

The semi-streaming algorithm samples edges once and constructs decompositions for multiple thresholds, achieving a high-probability approximation while using near-linear space; this version has linear update and query time.

  • (2 + ε)-approximation is obtained in a single pass with high probability using ˜O(n) bits of space.The algorithm outputs an approximation to the densest-subgraph value at the end of the stream.
  • The algorithm builds each decomposition by sampling edges, starting with Z1 = V and retaining nodes whose sampled degree exceeds (1−ε)αc log n.
  • Independent samples are partitioned across levels, and Chernoff bounds plus union bounds establish that high-degree nodes are retained while low-degree nodes are excluded with high probability.
  • O((n + m/d) poly log n) space suffices for constructing a decomposition at threshold d.
  • The streaming implementation maintains ˜Θ(n) independent ℓ0-samplers and an edge counter to obtain uniform edge samples and estimate m.
  • (2 + O(ε))-approximation follows after constructing decompositions across discretized thresholds and applying the decomposition guarantee.
  • ˜Θ(n) update time and ˜Θ(n) query time are required because every update changes all samplers and queries construct multiple decompositions.

4 A Dynamic Algorithm with Fast Update and Query Times

This section presents a deterministic dynamic algorithm that trades space and approximation quality for fast updates and queries while maintaining the densest-subgraph value.

  • The algorithm maintains O(log n) decompositions, whose combined update time is ˜O(1) and whose approximation is 4+O(ǫ).
  • (4 + ǫ)-approximation is maintained using ˜O(m + n) space, ˜O(1) amortized update time, and O(1) query time.
  • Each decomposition stores level-based neighbor lists and counters, with nodes marked dirty when decomposition degree conditions are violated.
  • RECOVER() repairs dirty nodes after updates, while a potential function pays for level changes and establishes the amortized update bound.
  • The data structure uses O(n + m) space because every edge appears in linked lists associated with both endpoints.

5 A Semi-Streaming Algorithm with Fast Update and Query times

This section contrasts a space-efficient semi-streaming algorithm with a faster dynamic algorithm, motivating a combined method that retains fast updates, small space, and queries during the stream.

  • The semi-streaming algorithm provides a (2 + ǫ)-approximation with ˜O(n) space but ˜Θ(n) update and final-query times.
  • The dynamic algorithm provides a (4 + ǫ)-approximation with ˜Θ(m + n) space, ˜O(1) update and query times, and queries at any time.
  • The combined algorithm targets a (4 + ǫ)-approximation with ˜O(1) update and query times, ˜O(n) space, and queries available during the stream.

5.1 An Overview of Our Result

The overview combines random edge sampling with dynamic decompositions to maintain a densest-subgraph approximation throughout a polynomial-length update stream using near-linear space and constant amortized update time.

  • Theorem 5.1 processes T updates with high probability using ˜O(n) bits of space.
  • The total processing time is ˜O(T), yielding ˜O(1) amortized update time.
  • At every time-step, the maintained output is a (4 + ǫ)-approximation, with O(1) query time.
  • The guarantee applies to a polynomial number of time-steps because the analysis uses a union bound over all times.
  • The approach combines ˜O(n) random samples with (α, d, L)-decompositions, while classifying time-steps as sparse or dense.
  • Maintaining the samples efficiently, adapting degree thresholds as edge counts change, and constructing decompositions from samples are identified as technical challenges.

5.2 Maintaining the randomly sampled edges in ˜O(1) update time

The sampling procedure maintains either all edges in sparse states or near-linear random samples in dense states, using hashing and streaming samplers to achieve near-linear space and polylogarithmic update time.

  • Randomly assigning edges to buckets and sampling each bucket yields a near-uniform sample while affecting only one bucket per update.
  • The algorithm maintains the entire edge set during sparse time-steps and ˜Θ(n) uniform samples during dense time-steps.
  • The bucket-and-sampler scheme uses ˜O(n) space and ˜O(1) worst-case update time.
  • For sparse states, the maintained subset equals the full edge set with high probability when m(t) ≤ 8αc^2n log^2 n.
  • The dense-state sampler provides negatively associated inclusion indicators and limits each update to at most two changes in the maintained sample.
  • Hashing partitions edges into buckets, while independent samplers produce the maintained subset and support constant-time hash evaluation.

5.3 A high level overview of our algorithm: Sparse and Dense Intervals

The algorithm partitions stream time-steps into dense and sparse intervals, using separate subroutines to maintain a (4 + ε)-approximation in each regime. These components together establish the main result.

  • Supporting components: P1 and P2 maintain the edge sets used by the sparse- and dense-interval procedures, respectively.P1 implements Theorem 5.2, while P2 maintains ˜Θ(1) independent copies of Theorem 5.3.
  • Interval classification: P3 classifies each time-step online, partitioning the stream into maximal contiguous dense and sparse intervals.The classification requires only a counter tracking the current number of edges, with ˜Θ(1) space and Θ(1) update time.
  • Interval classification: Sparse and dense classifications are based on edge-count thresholds of 8αc^2n log^2 n and 4αc^2n log^2 n, respectively.With high probability, sparse steps have at most the first threshold’s number of edges, while dense steps have at least the second threshold’s number.
  • Interval decomposition: The algorithm uses separate subroutines for sparse and dense time-steps, combining their guarantees to prove Theorem 5.1.P3 classifies time-steps online, while P4 and P5 maintain the output in the corresponding intervals.

5.4 Algorithm for sparse intervals

During sparse intervals, the algorithm combines an edge-maintenance sampler with Dynamic-algo to maintain a (4 + ε)-approximation using near-linear space and amortized constant-update time.

  • Guarantees: Theorem 5.4 maintains a (4 + ε)-approximation at every sparse time-step using ˜O(n) space, with high probability.The maintained output is defined throughout sparse time-steps t ≤ T.
  • Guarantees: ˜O(T) total processing time yields ˜O(1) amortized update time over T stream updates.The sparse-interval analysis charges initialization and interval computation across mutually disjoint intervals.
  • Method: The sparse-interval algorithm runs Theorem 5.2 to maintain F(t) = E(t) with high probability at sparse time-steps.This subroutine has ˜O(1) worst-case update time and ˜O(n) space.
  • Method: Dynamic-algo processes (V, F(t)) during each sparse interval, allowing the algorithm to maintain the sparse-step output.Because F(t) equals the current edge set throughout such an interval with high probability, Dynamic-algo operates on the relevant graph.
  • Time analysis: For a sparse interval ending before T, the computation is ˜O(n + (t1 − t0)) and becomes ˜O(t1 − t0) because the interval length is Ω(n).Intervals ending at T are handled separately, preserving the overall amortized bound.

5.5 Algorithm for dense intervals

During dense intervals, the algorithm maintains sampled edge sets and layered node decompositions, preserving their validity with high probability while achieving near-linear space and amortized polylogarithmic update time.

  • Decomposition: The dense-interval method maintains an (α, d(t)_k, L)-decomposition for each discretized index k ∈ [K].The density range is discretized in powers of (1 + ε), and K = ˜O(1).
  • Complexity: Theorem 5.6 uses ˜O(n) bits of space, while its sampling subroutine has ˜O(1) worst-case update time and ˜O(n) space.The overall dense-interval result follows from the correctness, space, and amortized-time analyses of its components.
  • Method: It maintains L node subsets Z(t)_1, ..., Z(t)_L using L − 1 mutually independent sampled edge subsets and degree-based level updates.Z(t)_1 is initialized as V, and subsequent sets are constructed from sampled-edge degrees.
  • Interval processing: Initialization prepares the decomposition before a dense interval, and RECOVER-SAMPLE(t) updates it after each graph change.The recovery procedure uses the prior decomposition together with newly updated samples.
  • Correctness: With high probability, the maintained tuple remains a valid (α, d(t)_k, L)-decomposition throughout each dense interval.Lemma 5.8 obtains the interval-wide statement by combining per-time-step guarantees with a union bound.

5.5.4 Data structures for implementing the procedure in Figure 4

The implementation stores sampled-neighborhood lists, degree counters, and dirty-node lists to update layered decompositions efficiently after stream changes.

  • Data structures: For each node and sample index, Friends lists store sampled neighborhoods associated with the relevant decomposition levels.The lists are empty above the applicable level and encode sampled neighbors at or below it.
  • Data structures: Degreei[v] counts sampled neighbors in Friendsi[v, i], while Dirty-Nodes[i] tracks nodes requiring level-related updates.The degree counter is zero when a node’s level is below i.
  • Sampling representation: Each edge appears at most once in any sample Si and at most L − 1 times across all maintained samples.This bounds the total sampled-edge representation used by the data structures.
  • Update handling: A graph update causes at most two changes in each Si, so all sampled-set and list updates take ˜O(1) time.Across L − 1 samples, this gives at most O(L) = ˜O(1) changes per stream update.
  • Level maintenance: Each main-loop iteration changes node levels and updates the associated Friends and Dirty-Nodes structures.Nodes move upward when sampled degree is high and downward when sampled degree is low.
  • Space complexity: The procedure uses ˜O(n) space because each of the L − 1 sampled edge sets has at most s edges.The resulting space is (L − 1) · s = ˜O(n).

5.5.6 The amortized update time of Dynamic-Stream during a dense time-interval

During a dense time-interval, Dynamic-stream uses a high-probability event to align sampled-edge degrees across levels, then applies a potential-function analysis to obtain near-constant amortized update time.

  • Analysis roadmap: The analysis proceeds by defining an event F that makes degrees across different sampled-edge subsets approximately consistent.This consistency extends the potential-function analysis to the multi-level randomized setting.
  • Amortized update time: ˜O(1) amortized update time follows because the potential decrease pays for the computation performed during recovery.Over a dense interval [t0, t1], the total time is ˜O(n + (t1 − t0)).
  • Analysis roadmap: With high probability, event F holds simultaneously across relevant level pairs and time-steps.The proof applies concentration bounds and a union bound over levels and time-steps.
  • Potential-function analysis: Conditioned on F, each input edge update changes the potential B by ˜O(1), while computation in the recovery procedure causes B to decrease.The potential B sums node and edge potentials associated with the level assignment and sampled edge sets.

5.5.8 Proof of Lemma 5.13

The proof bounds recovery cost by showing that potential changes from updates are small, while node promotions and demotions create sufficient potential decreases to pay for recovery work.

  • Proof structure: Parts (a) and (b) hold independently of F; only the potential decrease argument for part (c) conditions on F.This separates update-cost bounds from the event-dependent recovery analysis.
  • Amortized bound: O(tL/ǫ) total recovery time over t updates yields amortized update time O(L/ǫ).The level count satisfies L = ˜O(1), and the data structure uses O(n + m) space on the derived graph.
  • Potential changes: ˜O(1) bounds the potential change caused by inserting or deleting one edge from a sampled set.The change combines endpoint node potentials and the affected edge potential.
  • Potential changes: Each constant amount of computation in recovery causes the overall potential B to drop by Ω(1).For promotions, edge potentials decrease and node potentials do not offset the decrease; demotions are handled analogously.

6 Extension to Directed Graphs

The paper extends its dynamic densest-subgraph framework to directed graphs by transforming them into bipartite derived graphs, obtaining deterministic approximation and update guarantees.

  • Directed density: Directed-pair density is ρ(X, Y) = |E(X, Y)|/(|X||Y|), allowing X and Y to overlap.The densest directed subgraph maximizes this quantity over node subsets.
  • Guarantees: (8 + ǫ)-approximation is maintained deterministically with ˜O(m + n) space, ˜O(1) amortized update time, and O(1) query time.The approximation follows from the decomposition analysis and the resulting 4α · (1 + ǫ)^(3/2) bound.
  • Derived graph: The derived graph replaces each original node v with source node sv and target node tv, mapping (u, v) to (su, tv).This creates a bipartite representation with source-side zero in-degree and target-side zero out-degree.
  • Derived graph: The transformation preserves density: ρ′(S, T) = ρ(S, T), so the directed problem becomes densest-pair computation in the derived graph.The derived graph can be maintained using O(m + n) space and O(1) update time.
  • Directed decomposition: An (α, dS′, dT′, L)-decomposition uses nested source and target node families with separate degree thresholds.Nodes are retained when their degrees exceed α times the corresponding threshold and removed when degrees fall below it.

7 Sublinear-Time Algorithm

In the incidence-list model, the paper gives a sublinear-time (2 + ǫ)-approximation algorithm and proves query lower bounds for stronger approximations.

  • Oracle model: The incidence-list oracle supports degree queries and queries for the ith neighbor of a node.This representation provides efficient access without requiring the algorithm to read the entire input graph.
  • Upper bound: ˜O(n) oracle queries, time, and space suffice to compute a (2 + ǫ)-approximate densest subgraph.The algorithm samples ˜O(n) edges and processes them using decompositions for several density scales.
  • Lower bound: For the constructed communication problem, a sublinear-time algorithm using q oracle queries implies a ˜O(q)-bit communication protocol.The construction uses disjoint star-or-clique subgraphs whose incident edges are distributed among players.
  • Lower bound: ˜Ω(n/λ^2) queries are necessary for any λ − ǫ approximation when λ ≥ 3/2.The lower bound is obtained by reducing a communication-complexity problem to oracle queries.

8 Distributed Streams

In distributed streaming, the paper uses a sampled edge sketch to maintain a (2 + ε)-approximate densest subgraph with low communication and space.

  • Distributed streaming: The sketch samples ˜O(n) edges without replacement for coordinator-side computation.The sampling algorithm supports ˜O(k + n) bits of communication.
  • Distributed streaming: (2 + ε)-approximate densest subgraph solutions require ˜O(k + n) bits of communication in the distributed streaming setting.The coordinator uses ˜O(n) space, while each site uses ˜O(1) space.
  • Distributed streaming: The coordinator needs ˜O(n) space and each site needs ˜O(1) space.These resource bounds accompany the (2 + ε)-approximate solution.

9 Open problems

The paper identifies unresolved questions about the approximation ratio, update-time guarantees, hardness of approximation, and extending space- and time-efficient dynamic methods to other graph problems.

  • Approximation and complexity: Whether the algorithm’s (4 + ε) approximation ratio is tight remains open, including whether it can be improved to (2 + ε).Matching (2 + ε) is known to be interesting even with larger space complexity.
  • Approximation and complexity: Hardness results for approximation algorithms remain an open problem; currently, hardness is known only for maintaining the optimal solution.The paper also asks whether polylogarithmic worst-case update time is achievable.
  • Extensions: A broader open direction is obtaining similarly space- and time-efficient fully-dynamic algorithms for maximum matching and single-source shortest paths.The question concerns extending the paper’s approach beyond densest subgraph.
Loading 1504.02268v3…