Implementation and evaluation of space-efficient traversal algorithms on succinct de Bruijn graphs

Technical Summary: Implementation and Evaluation of Space-Efficient Traversal Algorithms on Succinct de Bruijn Graphs

Problem Statement
Succinct de Bruijn graphs (dBGs) allow metagenome assemblers to store k-mer graphs at near information-theoretic minimums (e.g., 4–5 bits per edge), enabling the processing of massive datasets on modern hardware. However, standard traversal algorithms, specifically Breadth-First Search (BFS) and Depth-First Search (DFS), negate these memory savings. Traditional BFS requires a $\Theta(N \log N)$ bit distance array (one word per node), and traditional DFS requires a $\Theta(N \log N)$ bit stack of node identifiers. For large graphs, this auxiliary storage can exceed the size of the graph representation itself. While space-efficient traversal methods achieving $O(N)$ bits have existed theoretically for a decade (e.g., Elmasry-Hagerup-Kammer), they had not been implemented or evaluated on succinct dBGs.

Methodology
The authors implemented and evaluated two space-efficient traversal algorithms on MEGAHIT's succinct de Bruijn graph (SDBG) representation, which utilizes the BOSS encoding with Burrows-Wheeler rank/select navigation.

1. Space-Efficient BFS:

   • Mechanism: Replaces the standard 32-bit distance array with a one-bit-per-node visited bitmap and two frontier arrays.
   • Distance Handling: Instead of storing distances, the algorithm passes computed distances to a callback function, eliminating the need for a global distance array.
   • Navigation: Uses $O(1)$ rank/select operations for forward navigation.
   • Auxiliary State: Consists of the visited bitmap and a frontier array. The frontier size is bounded by the widest level of the BFS, which is typically manageable in near-linear genome assembly graphs.

2. Space-Efficient DFS (EHK-style):

   • Mechanism: Reconstructs the recursion stack during backtracking rather than storing a stack of node identifiers.
   • State Representation: Uses a two-bit color for visited states (via a choice dictionary) and a two-bit symbol per node to record the incoming edge from the parent.
   • Parent Recovery: During backtracking, the algorithm identifies the parent by matching the stored symbol against the node's incoming edges (at most 4 in a dBG). This process is unambiguous due to distinct edge labels.
   • Auxiliary State: Requires 4 bits per node, independent of traversal depth.

Experimental Setup

• Graphs: Three graphs were constructed at $k=23$. Two small graphs ($N \approx 400k$ and $10.6M$) were used to verify correctness against textbook baselines. One large graph ($N = 807,721,414$ edges) was used for performance evaluation.
• Environment: Experiments were run on a laptop (AMD Ryzen 9 6900HS, 16 GB RAM) under WSL2, with the graph stored on an HDD. Code was compiled with g++ -O2 -march=native.
• Metrics: Memory usage was measured via VmHWM from /proc. Correctness was verified by comparing node entry/exit orders and parent relationships against standard implementations.

Key Results
On the large graph ($807.7$ million edges), both space-efficient and standard traversals reached the same 587 million nodes (72.7% of the graph).

• Memory Reduction:

  • BFS: The space-efficient version used 2.07 GiB compared to 4.87 GiB for the standard version, a 2.36× overall reduction. The auxiliary state alone was reduced by 11× (from a 3.01 GiB distance array to a 96 MiB bitmap + 193 MiB frontier).
  • DFS: The space-efficient version used 2.16 GiB compared to 3.55 GiB for the standard version, a 1.64× overall reduction. The auxiliary state was reduced by 4.7× (replacing a 1-byte state array and 1.0 GiB node stack with a 0.38 GiB 4-bit representation).
  • Theoretical Model: The paper notes that the overall reduction is bounded by the graph size. For a graph with $g$ bytes per edge, the reduction ratio is modeled as $\frac{g+4.09}{g+0.376}$. At MEGAHIT's rate of 2.37 bytes/edge, the model predicts a 2.35× reduction, closely matching the measured 2.36×.

• Time Performance:

  • BFS: The space-efficient version was slightly faster (12.6 min) than the baseline (13.8 min).
  • DFS: The space-efficient version was slower (32.4 min) compared to the baseline (19.0 min). This overhead is attributed to the $O(k)$ complexity of backward navigation required for parent recovery during backtracking.

Significance and Claims
The paper claims that the primary benefit of these algorithms lies in the auxiliary state, which no longer scales with the identifier width ($\Theta(N \log N)$) but rather linearly ($O(N)$).

• Scalability: The ratio of space savings grows with graph size ($\log N$), making these methods increasingly valuable for larger datasets.
• Depth Independence: The space-efficient DFS state is independent of traversal depth, removing the data-dependent node stack and bounding the worst-case memory usage.
• Practicality: While the DFS incurs a time penalty due to parent recovery, the BFS achieves space savings without increasing running time. The authors emphasize that the total process memory reduction is limited by the graph representation size; however, as succinct representations become more compact, the relative benefit of these space-efficient traversals increases.

The work provides a concrete implementation and empirical validation of theoretical space-efficient traversal methods on real-world metagenomic data, demonstrating that significant memory savings are achievable without altering the underlying graph structure.