Making graphs compact by lossless contraction

Area of Science:

• Graph theory
• Data structures
• Algorithms

Background:

• Large graphs pose significant challenges for storage and query processing.
• Existing methods often struggle with scalability and efficiency for complex graph analytics.

Purpose of the Study:

• To propose a novel graph contraction scheme for reducing large graphs to smaller, compact representations.
• To enable efficient querying and analysis on these reduced graph structures.
• To demonstrate the scheme's applicability across diverse graph query types and its lossless nature.

Main Methods:

• Contracting obsolete parts and regular structures into supernodes, each containing a synopsis for query classes.
• Identifying and contracting regular structures specific to different graph types.
• Adapting existing query algorithms (subgraph isomorphism, triangle counting, etc.) to work with contracted graphs.
• Developing a bounded incremental contraction algorithm for efficient updates.

Main Results:

• The contraction scheme achieves an average graph size reduction of 71.9%.
• Significant query evaluation speedups were observed, including 2.24x for connected component queries.
• The contracted graph representation is generic, lossless, and supports multiple query classes simultaneously.

Conclusions:

• The proposed graph contraction scheme offers a powerful and efficient method for handling large graphs.
• It provides a compact, lossless representation that enhances query performance across various analytical tasks.
• The scheme is adaptable and supports incremental updates, making it suitable for dynamic graph environments.