Scaling Graph Compression: Parallel Dense Subgraph Mining via BSP

TL;DR

As Web and social networks swell to billions of nodes, the "memory wall" becomes a critical bottleneck. This paper introduces a parallelized version of the Dense Subgraph Mining (DSM) algorithm. By utilizing the Bulk Synchronous Processing (BSP) model and dynamic load balancing, the authors achieve massive speedups in graph edge reduction and compression, maintaining the state-of-the-art space/time efficiency for neighbor queries.

Problem & Motivation: The Scalability Crisis in Graph Mining

Modern graphs—like the Web graph with its 200+ billion edges—are too large for single-machine memory but too complex for slow disk access. Current compression techniques (e.g., k2-trees, LLP) often rely on sequential preprocessing that doesn't scale. While MapReduce and Pregel offer distributed frameworks, they often suffer from high communication overhead during the iterative phases required to find dense patterns like cliques or bicliques.

The authors identify a specific opportunity: Locality. Web graphs exhibit high similarity in adjacency lists. If we can find these dense "clusters" in parallel without losing too much global information, we can replace thousands of edges with a single "virtual node," drastically reducing the graph's footprint.

Methodology: Parallelizing Dense Subgraph Mining (DSM)

The authors propose two refined parallel algorithms based on the BSP model, which organizes computation into supersteps of local processing, global communication, and barrier synchronization.

1. Edge Reduction with Virtual Nodes (Algorithm 1)

This algorithm focuses on reducing the total number of edges before applying standard compression (like k2-trees).

• Step 0: Each processor identifies local dense subgraphs $H(S,C)$ where every node in $S$ connects to every node in $C$.
• Step 1: To ensure consistency across the cluster, a master node relabels local virtual node IDs into a global namespace.
• Step 2: Processors replace the original edge blocks with these new global virtual nodes.

Above: The sequential DSM logic where adjacency lists are inserted into a prefix tree to find high-frequency patterns.

2. Extraction with Dynamic Load Balancing (Algorithm 2)

Social networks are notoriously "skewed" (some nodes have millions of connections, others have two). Algorithm 2 introduces a Dynamic Load Balancer:

• Periodically, processors report their workload (number of subgraphs found and current threshold).
• If the "workload gap" between the busiest and idlest processor exceeds a threshold, data is migrated across the network.

Experiments & Results: Efficiency at Scale

The algorithms were tested on a 64-processor cluster using datasets like indochina and arabic-2005.

Speedup and Scalability

The results confirm that the parallel approach scales effectively, particularly for larger graphs which benefit more from memory aggregation. For the uk-2002 dataset, the speedup reached 102.87x using 64 processors, indicating super-linear efficiency likely due to improved cache utilization.

Compression Integrity

A major concern in parallel graph mining is Edge Ratio (ER): do we lose dense subgraphs because they are split across processors? The study shows an ER of 0.96 to 0.99 for Web graphs, meaning almost no compression efficiency was sacrificed for speed.

Figure: The charts show that as the number of processors increases, running time drops sharply while "bits per edge" (bpe) remains stable.

Critical Insight & Conclusion

The Takeaway: Parallelizing DSM using the BSP model is highly effective because Web graphs have a high degree of structural locality. By mining these patterns locally and synchronizing only for virtual node ID assignment, we can compress massive graphs in a fraction of previous times.

Limitations: The research notes that while the mining is parallel, some subsequent steps (like final k2-tree construction) remain sequential. This creates a bottleneck as the number of processors grows, a classic example of Amdahl's Law in action. Future work should focus on fully distributed construction of the underlying compact data structures (bit vectors and rank/select structures) to unlock the next level of scalability.