Hub labeling makes exact distance calculation practical for large human pangenome graphs

Technical Summary: Hub Labeling for Pangenome Graph Distance Queries

Problem Statement
Pangenome graphs have become the standard for representing population variation, yet efficient exact distance calculation between graph positions remains a bottleneck. Tools like the vg toolkit rely on fast minimum-distance queries for operations such as seed clustering during read alignment. The existing baseline distance index decomposes the graph into nested subgraphs called "snarls" and stores a dense all-pairs distance matrix for each snarl. This approach suffers from quadratic space complexity relative to the number of children in a snarl. Consequently, large, complex snarls common in human pangenome graphs dominate the index size, often rendering whole-genome indexing impractical. To mitigate this, the baseline method imposes a size limit, omitting distance matrices for oversized snarls and forcing runtime graph traversals for queries involving them. This creates an unsatisfactory trade-off between index size and query completeness.

Methodology
The authors propose replacing the dense distance matrices for oversized snarls with hub labeling (also known as 2-hop labeling), a technique previously validated for large directed graphs but not applied to bidirected sequence graphs. The methodology involves three key technical adaptations:

1. Directed Representation of Net Graphs: Since hub labeling algorithms are defined for directed graphs, the authors introduce a directed representation of the bidirected "net graph" within each snarl. In this representation, shortest path lengths correspond to the minimum walk lengths in the original bidirected net graph.
2. Label Construction via Pruned Landmark Labeling: Labels are built using pruned landmark labeling. To optimize label size, the authors employ contraction hierarchies to determine the order in which vertices are processed as hubs. Vertices are contracted based on an importance score (heuristic from road network literature), and the reverse of this contraction order is used to build labels. This ordering prioritizes "important" vertices (those likely to lie on many shortest paths) early in the process, facilitating more effective pruning during the Dijkstra traversals used to generate labels.
3. Storage and Querying: The resulting labels are stored in a columnar, bit-packed format within the distance index. Queries are resolved by intersecting the forward and backward labels of the source and destination nodes, calculating the minimum sum of distances via shared hubs.

Key Contributions

• First Application to Bidirected Graphs: This work presents the first application of hub labeling to bidirected sequence graphs, requiring a novel transformation of snarl net graphs into directed representations.
• Scalable Indexing: The method enables the indexing of every snarl in large pangenome graphs, eliminating the need to drop distances for complex regions.
• Integration with vg: The algorithm is integrated into the vg toolkit's distance index infrastructure (libbdsg), supporting both chromosome-scale and whole-genome pangenomes.

Results
The authors evaluated the approach on four human chromosome pangenomes and four human whole-genome pangenomes:

• Space Efficiency: On chromosome graphs, the hub-labeling index (at a snarl limit of 500) required between 0.9 GB and 3.0 GB. This represents a 28× to 119× reduction in space compared to the estimated size of dense matrices required for snarls with more than 500 children. For whole-genome graphs, the authors successfully built indexes ranging from approximately 45 GB to 90 GB in under 6 hours, whereas dense matrices were estimated to require multiple terabytes.
• Query Completeness: The hub-labeling index could answer 3% to 18.6% of node-to-node queries that the baseline index could not answer (due to oversized snarls).
• Query Performance: On queries answerable by both methods, the median query time distributions broadly overlapped. While some outliers were observed, the general performance was comparable to the baseline.
• Build Time: Index construction times were practical, ranging from roughly 36 minutes to 5.1 hours for whole-genome graphs, depending on the snarl size limit and graph complexity.

Significance and Claims
The paper claims that hub labeling makes the construction of complete, exact distance indexes practical for large and topologically complex pangenome graphs. By replacing quadratic dense matrices with sublinear hub labels for oversized snarls, the method removes the trade-off between index size and the ability to answer queries in complex regions. The authors suggest that pangenome graphs likely possess "low highway dimension" (similar to road networks), a property that makes hub labeling effective. They conclude that this advancement allows for the indexing of whole-genome pangenomes in feasible space and time, enabling downstream applications like read mapping that previously struggled with incomplete distance data. The authors remain modest, noting that further optimization may be required for downstream mappers to fully leverage these large indexes and that the specific contraction hierarchy heuristics used were not retuned for pangenome graphs.