Compressed Foundations: Leveraging Dense Subgraphs for Scalable Social and Web Graphs

TL;DR

This research tackles the "Big Graph" storage crisis by moving beyond simple adjacency list compression. By mining the graph for dense subgraphs (structures where sets of nodes are highly interconnected), the authors reduce the storage cost of edges from $O(|S|\cdot |C|)$ to $O(|S|+|C|)$. The result is a compact, searchable structure that outperforms standard baselines like WebGraph in symmetric navigation tasks.

The "In-Neighbor" Tax

Most graph compression algorithms exploit locality (nodes linking to nearby nodes) and similarity (nodes sharing similar links). While effective, these methods are often asymmetric. If you want to know who points to a specific user on a social network, you usually need to store the entire graph again in its transposed form. This "in-neighbor tax" effectively doubles the memory footprint.

The authors argue that we shouldn't just compress lists; we should compress the motifs that create those lists.

Methodology: The Power of $H(S,C)$

The core innovation lies in the definition of a Dense Subgraph $H(S,C)$. Unlike a clique (where every node connects to everyone else in the same set) or a biclique (where one set connects entirely to a different set), a dense subgraph allows $S$ and $C$ to overlap arbitrarily.

The Two-Stage Discovery

1. Clustering: Using "shingles" (hash-based fingerprints), the algorithm groups nodes with similar adjacency patterns.
2. Mining: Inside each cluster, a frequent itemset mining algorithm identifies specific node sets that form dense patterns.

Compact Representation

Once found, a subgraph is stored as a sequence $X$ composed of three parts:

• L: Nodes in $S$ but not in $C$.
• M: Nodes in both $S$ and $C$ (the overlap).
• R: Nodes in $C$ but not in $S$.

By using a Wavelet Tree for the sequence $X$ and an RRR-compressed bitmap for the delimiters, the graph becomes a set of searchable integers.

Figure 1: Comparison between standard edge lists and the proposed compact L/M/R representation.

Performance and SOTA Comparison

The authors tested their approach on massive datasets like LiveJournal and UK web crawls.

• Space Efficiency: For web graphs, the approach achieved compression as low as 1.49 bits per edge. Crucially, it was often smaller than the WebGraph (BV) format even when BV didn't support in-neighbor queries.
• Query Speed: While the $k^2$-tree remains faster for simple out-neighbor lookups in some scenarios, the dense subgraph approach provides a more balanced "Space/Time Tradeoff" for social networks.

Table 1: Compression performance (bits per edge) across different datasets. Note the significant gains in the 'bpe' column for H+R combined.

Critical Insight: Why it Works

The trick is the $RE/|X|$ ratio (Edges captured divided by integers stored). In web graphs, this ratio can be as high as 14.17, meaning for every node ID we store, we represent 14 edges. This "structural amplification" is the secret to beating entropy-based compression alone.

Conclusion & Perspective

The transition from literal edge storage to pattern-based storage is essential as we move toward graphs with trillions of edges. While the construction time (mining subgraphs) is higher than simple sorting, the dividends in memory savings and "mining-ready" storage—where you can find communities directly in the compressed data—make this a cornerstone work for academic and industrial graph systems.

Limitations: The discovery phase is computationally heavy (approx. 0.1ms per link). Future improvements could benefit from parallelizing the frequent itemset mining step.