iRun: Horizontal and Vertical Shape of a Region-Based Graph Compression

Area of Science:

• Computer Science
• Data Science
• Graph Theory

Background:

• Real-world graphs, such as social networks, are massive and computationally intensive.
• Existing graph compression methods struggle with sparse graphs, leading to suboptimal compression ratios.
• Current state-of-the-art (SOTA) approaches decompose graphs into fixed-size submatrices, which is inefficient for power-law distributed graphs.

Purpose of the Study:

• To develop an advanced ordered matrix compression technique for large-scale graphs.
• To improve graph compression ratios by addressing the limitations of fixed-size submatrix decomposition.
• To enhance computational and memory efficiency in processing massive graph data.

Main Methods:

• The proposed method divides graph matrices into variable-shape sub-blocks, rather than fixed-size ones.
• It considers both horizontal and vertical shaped regions for optimized compression.
• This deep-level division aims to minimize empty cell processing and maximize compression efficiency.

Main Results:

• The novel approach achieved an average compression ratio of 93.8%.
• This represents a significant improvement over existing SOTA graph compression techniques.
• Empirical evaluations demonstrate the effectiveness of variable-shape region compression for sparse graphs.

Conclusions:

• Variable-shape region decomposition is a superior strategy for ordered matrix compression in large graphs.
• The proposed method offers substantial improvements in compression ratio and efficiency for real-world graph data.
• This research provides a more effective solution for handling the computational challenges of massive graph processing.