RowDiff

RowDiff compresses annotation matrices on large labeled graphs by sparsifying and encoding graph labels with linear time and space complexity.

Key Features:

• Linear-Time Graph Annotation Compression: Constructs compressed representations in time linear to the number of vertices and labels, with space proportional to graph size, supporting graphs with trillions of nodes.
• Sparsification with multi-BRWT Integration: Performs an intermediary sparsification step on annotation matrices and integrates with multi-BRWT compressed binary representations to reduce annotation footprint.

Scientific Applications:

• Large-Scale Genomic Graph Annotation: Enables efficient storage and processing of labeled graphs in genomics, transcriptomics, and metagenomics sequencing datasets.

Methodology:

RowDiff transforms graph annotation matrices through sparsification, then applies compressed binary encoding compatible with multi-BRWT, achieving parallelizable and distributed construction with substantial reduction in storage requirements.