Source-linked AI summary
Densest Subgraph in Streaming and MapReduce
Bahman Bahmani, Ravi Kumar, Sergei Vassilvitskii
TL;DR
The paper addresses how to find dense subgraphs in massive graphs when conventional algorithms do not scale. It develops streaming and MapReduce algorithms, obtaining provable approximation guarantees with few passes and demonstrating scalability on real-world graphs.
Problem
Finding dense subgraphs is important across graph-data applications, but existing guaranteed algorithms are not efficient for massive datasets.
Method
The paper adapts greedy densest-subgraph principles into streaming algorithms using basic graph parameters and parallelizes them in MapReduce.
Results
The algorithms provide a (2+epsilon)-approximation in O((log n)/log (1+epsilon)) passes, with experiments showing scalability on massive real-world graphs.
Takeaways & Limitations
The algorithms combine provable guarantees with practical scalability for graphs containing billions of edges.
Takeaways & Limitations
Observed graphs do not attain the worst-case pass or approximation bounds, and explaining this behavior remains outside the paper’s scope.
Abstract
from arXiv · showhide
The problem of finding locally dense components of a graph is an important primitive in data analysis, with wide-ranging applications from community mining to spam detection and the discovery of biological network modules. In this paper we present new algorithms for finding the densest subgraph in the streaming model. For any epsilon>0, our algorithms make O((log n)/log (1+epsilon)) passes over the input and find a subgraph whose density is guaranteed to be within a factor 2(1+epsilon) of the optimum. Our algorithms are also easily parallelizable and we illustrate this by realizing them in the MapReduce model. In addition we perform extensive experimental evaluation on massive real-world graphs showing the performance and scalability of our algorithms in practice.
1. INTRODUCTION
The paper targets densest-subgraph computation on massive graphs, where streaming and distributed models are needed for applications including community mining, biology, and spam detection. It adapts existing approximation principles into scalable algorithms with provable guarantees and MapReduce parallelization.
- Motivation: Densest-subgraph computation supports applications in community mining, computational biology, spam detection, and reachability or distance-query indexing.These applications generally require approximation guarantees rather than unsupported heuristics.
- Contributions: The paper focuses on graphs that cannot fit in main memory and develops algorithms that generalize to graphs with billions of nodes and tens of billions of edges.The approach computes basic graph parameters and is designed for MapReduce parallelization.
- Problem setting: The undirected problem seeks a node subset maximizing the ratio of internal edges to nodes, while the directed version selects source and target subsets using geometric-mean normalization.A size-constrained variant additionally requires the output subset to contain at least k nodes.
- Research gap: Existing algorithms provide good approximation factors but are inefficient on very large datasets, motivating streaming and distributed solutions.The paper identifies this as an open problem addressed by its new algorithms.
- Computational models: Streaming processes graph edges sequentially with sublinear RAM, whereas MapReduce partitions input across machines and repeats distributed computation in multiple passes.Both paradigms target inputs too large for conventional single-machine processing.
- Contributions: O((log n)/log (1+epsilon)) passes and a (2+epsilon)-approximation are guaranteed for the main streaming algorithm.The paper also reports extensions for size-constrained and directed densest-subgraph variants.
2. RELATED WORK
Prior work established exact and approximate densest-subgraph algorithms and adapted the problem to application-specific settings. Streaming and MapReduce research supplied the scalable computational paradigms that this paper combines with approximation guarantees.
- Densest-subgraph algorithms: Goldberg introduced the undirected densest-subgraph problem and used O(log n) flow computations for an exact solution.Charikar later gave a simpler greedy 2-approximation.
- Densest-subgraph algorithms: For directed graphs, prior work progressed from an O(log n) approximation to exact polynomial-time solution via O(n^2) linear programs and a combinatorial 2-approximation.The combinatorial algorithm was subsequently simplified.
- Application-specific variants: Densest-subgraph variants have been tailored to computational biology, community mining, and working-group selection.Large-scale web applications also used shingling heuristics to find high-neighborhood-overlap node sets without approximation guarantees.
- Streaming and MapReduce: Streaming assumes data is too large for main memory and processes objects sequentially, while MapReduce supports large-scale parallel processing across machines.These paradigms motivate scalable algorithms for massive graph inputs.
3. PRELIMINARIES
The preliminaries define graph density and approximation for undirected and directed graphs, including a size-constrained objective. They also introduce induced edges and degrees used to characterize dense subgraphs.
- Undirected graphs: For an undirected graph, the induced edge set E(S) contains edges whose endpoints both lie in subset S.The induced degree deg_S(i) counts induced edges incident to node i.
- Undirected graphs: Undirected density is defined from the induced subgraph, and the size-constrained objective maximizes density over subsets with at least k nodes.The weighted case incorporates total induced edge weight.
- Directed graphs: For a directed graph, E(S,T) consists of edges from source subset S to target subset T, which need not be disjoint.Directed density is defined over these two subsets.
- Approximation: An alpha-approximation for the undirected problem returns a subset whose density is at least the optimum density divided by alpha.The same approximation concept extends analogously to directed graphs.
4. ALGORITHMS
The paper develops streaming algorithms for approximately finding densest subgraphs, relaxing greedy deletions to reduce passes while retaining provable guarantees. The algorithms support undirected, directed, and size-constrained variants, with matching space lower bounds and MapReduce-oriented scalability.
- Streaming algorithms: O(log n) passes and O(n) memory yield a (2 + 2ϵ)-approximation for undirected and directed densest subgraphs.The size-constrained variant obtains a (3 + 3ϵ)-approximation in the general case.
- Streaming algorithms: Each pass removes nodes whose degree is below 2(1 + ϵ)ρ(S), recomputes density, and retains the densest intermediate graph.The algorithm only needs current node degrees and density, requiring O(n) memory in streaming.
- Approximation guarantee: ρ(S) ≥ ρ(S∗)/(2 + 2ϵ), so one intermediate subgraph achieves the stated approximation guarantee.The remaining graph’s density can be non-monotonic, so the algorithm tracks the best intermediate solution.
- Pass complexity: O(log1+ϵ n) passes suffice because each pass reduces the remaining node set by at least a factor of 1/(1 + ϵ).For small ϵ, this is approximately O((log n)/ϵ) passes.
- Lower bounds: Any p-pass α-approximation streaming algorithm with α ≥ 2 requires Ω(n/(pα^2)) space.Thus, achieving a constant-factor approximation in O(log n) passes requires Ω(n/log n) memory, nearly matching the algorithm’s O(n) usage.
5. PRACTICAL CONSIDERATIONS
The section addresses practical scalability through sketching-based memory reduction and MapReduce implementations. It explains the algorithmic primitives required for parallel execution and how node degrees and removals are computed.
- Memory reduction: Sketching techniques probabilistically summarize node degree distributions to reduce the space required by the streaming algorithms.The algorithm needs node degrees to decide which nodes to remove, motivating frequency-estimation sketches.
- Memory reduction: The sketch estimates a node’s degree by taking the median of multiple frequency estimates.The underlying data structure is used as a black box for maintaining item frequencies in the stream.
- Memory reduction: High-degree nodes receive precise estimates, while accidentally retaining a low-degree node is considered less harmful than prematurely removing a high-degree node.This asymmetric error tolerance matches the algorithm’s node-removal decisions.
- MapReduce implementation: The algorithms parallelize around three functions: computing graph density, computing node degrees, and removing nodes below a threshold.The MapReduce realization illustrates how these functions can exploit distributed computation.
- MapReduce implementation: MapReduce computes degrees by duplicating each edge in both directions, grouping neighbors by node, and counting associated values.Each reducer outputs the degree for its key.
- MapReduce implementation: Node removal and incident-edge filtering are implemented in two MapReduce passes, retaining exactly edges whose endpoints are both unmarked.The first pass marks nodes and filters by first endpoint; the second pivots on the second endpoint.
6. EXPERIMENTS
Experiments on large social-network graphs evaluate approximation quality, pass counts, graph shrinkage, directed-graph settings, sketching, and scalability. The algorithms achieve better-than-guaranteed practical approximation, reduce passes substantially for moderate epsilon, and scale to massive graphs.
- 6.1 Data description: Four large social networks—flickr, im, livejournal, and twitter—form the basis of almost all experiments.The graphs represent photo-sharing, messaging contacts, friendship, and follower networks, respectively.
- 6.2 Approximation quality: The approximation factors are much better than the theoretical guarantee of Lemma 3 on seven moderately sized undirected SNAP graphs.The optimum density is obtained through an LP formulation whose value equals the optimal solution value, ρ∗(G).
- 6.3 Undirected graphs: ϵ ∈[0.5, 1] cuts the number of passes by half while losing only 10% of the optimum.The comparison uses density relative to the algorithm’s result at ϵ = 0.
- 6.3 Undirected graphs: The graph becomes dramatically smaller during the early passes, potentially allowing the remaining computation to run in main memory.This can avoid the overhead of additional passes.
- 6.4 Directed graphs: For directed graphs, evaluating powers of δ reduces the search over c values; the experiments fix δ = 2 and study livejournal and twitter.Trying all n^2 possible c values is prohibitive, while the resolution-based alternative worsens the approximation guarantee by at most a factor δ and takes 2 log n/ log δ time.
- 6.6 Scalability: The algorithms run in under 260 minutes on im and around 35 minutes per c value and iteration on twitter, demonstrating scalability.For twitter, the number of iterations is between four and seven and only a very small number of c values are tried.
7. CONCLUSIONS
The paper develops scalable streaming and MapReduce algorithms for dense subgraphs with provable guarantees, extending them to size-constrained and directed settings. Experiments show strong practical scalability and quality on very large graphs.
- Conclusions: The algorithms obtain a (2+ϵ)-approximation using a small number of passes in streaming and MapReduce.They use basic graph parameters and are designed for parallelization.
- Conclusions: Extensions handle subgraphs required to exceed a prescribed size and directed graphs.
- Conclusions: The experiments show scalable performance and quality often much better than the theoretical guarantees.
- Conclusions: The algorithm scales to a graph with more than a half billion nodes and six billion edges.The paper identifies scalability as the main reason this graph could be processed.