Beyond Bicliques: Revolutionizing Graph Compression via Dense Subgraph Mining

TL;DR

This research tackles the massive storage demands of Web and social graphs by identifying "dense subgraphs"—generalizations of cliques and bicliques. By factoring out these patterns into virtual nodes or sequence-based compact structures, the authors achieve unprecedented compression (down to 0.9 bits per edge) while supporting fast, bidirectional queries and in-situ graph mining.

Background: The Limits of Locality

Web graph compression has historically relied on locality (links pointing to the same domain) and similarity (pages having similar neighbor sets). However, as social networks grow, these assumptions falter. Social networks are "noisier," less local, and require bidirectional traversal (following and followers). The challenge is: can we find a structural primitive that compresses both Web and social networks effectively while allowing us to query them without full decompression?

The Core Insight: Dense Subgraphs

The authors shift from finding simple bicliques (two disjoint sets of nodes $S$ and $C$ where every node in $S$ points to every node in $C$) to dense subgraphs. This includes:

• Cliques: Where $S=C$.
• Bicliques: Where $S\cap C=\varnothing$.
• Overlapping sets: Where some nodes act as both sources and centers.

1. The Mining Process

To handle billion-edge scales, the paper utilizes a two-stage approach:

1. Clustering: Using "shingles" (fingerprints of adjacency lists) to group similar nodes.
2. Mining: A prefix-tree-based algorithm that identifies the most "profitable" subgraphs to compress within each cluster.

Methodology: Two Paths to Compression

Path A: Virtual Node Mining (VNM)

For Web graphs, the identified edges are replaced by a Virtual Node. If a set $S$ points to $C$, we insert a node $w$, creating edges $Sow$ and $woC$. This reduces $|S|imes|C|$ edges to $|S|+|C|$ edges. The resulting "reduced graph" is then encoded using the BFS-based ordering (Apostolico and Drovandi), which thrives on the simplified structure.

Path B: Sequence-Based Compact Structures

For social networks, the authors design a novel representation using Wavelet Trees and Bitmaps. Instead of altering the graph, they represent the dense subgraphs as a sequence $X$ (listing nodes in $S-C$, $S\cap C$, and $C-S$) and a bitmap $B$ for alignment. This allows for:

• In-place Mining: Queries like "list all cliques" or "find density" can be answered by scanning the compact bitmaps directly.

Experimental Showdown

The results demonstrate a clear split in strategy:

• Web Graphs: The combination of VNM and k2-trees (a sparse matrix decomposition technique) achieves the highest compression. In the indochina-2004 dataset, space drops to a staggering 0.87 bits per edge (bpe).
• Social Networks: On dblp-2011 and LiveJournal, the sequence-based structure + MPk provides the best space-time tradeoff, proving that community-based patterns are more effective for social data than URL-based orderings.

Critical Insight & Future Outlook

The genius of this work lies in its robustness. While most compression algorithms fail when the graph is "transposed" (reversing all edges), the dense subgraph approach is symmetric—it captures the same underlying community regardless of edge direction.

Limitations: The "Path B" approach (Sequence + WT) is slower (5–20 µs) than pure adjacency list methods. However, in the era of Big Data, the ability to fit a graph into RAM that previously required a disk-based distributed system is a paradigm shift in cost and speed.

Future Work: Integrating these patterns into dynamic graph systems where edges are added in real-time remains an open, high-value challenge.